I'm on a Mac, and have had zero problems. No you don't have to be wired, but if you're gonna stream HD shyt, the connection will have to be pretty fast.
The VERY FIRST thing you should do, if you weren't aware, is, on the PS3 XMB, go to Settings --> all the way down to Network Settings --> and make sure Media Server Connection is ENABLED.
Now, before I hit this next step, I'll say this. I use a static IP on my Mac, so it's always the same. If you don't, then every time you restart your cpu, it'll probably change IP addresses, and you may (I say may, cause I don't know. With a static IP, I don't have this problem) have to do this step again. If you don't know what your IP is (on a Mac), System Preferences --> Network --> and it'll show on the window that pops up under "IP Address".
Now, on the PS3 Media Server, open it up, and go to General Configuration --> Force Networking on Interface --> en0 (IP address will be here). You may have to force the IP address to get it to work (the next box down...I had to do this using an earlier version, but just using en0 worked fine on the newest version). Make sure you click the SAVE button at the top of the app window (whenever you do something, you must save before clicking a different tab, or what you did will revert back), and restart it.
Besides tinkering with some of the Navigation Settings (you'll of course wanna add the folders you intend to share), that's really all that needs to be done. You shouldn't have to "search for Media Servers" as it pops right up for me. Also, my TV is able to connect to my network, and this program sees my TV, my TV sees it, so I can cut out the middle man (PS3) and stream right to the TV, which is nice.
I think that's it. If you're still having problems, post 'em and I'll do my best to help.