If you don't see any Peers on the first screen after 20 seconds then you have connection problems (wether you are on WiFi or 3G, make sure sure that you have a good signal and a robust internet connection)
Once you see at least 1 peer (other than yourself) on the Browse tab, then your searches should work.
If you want to make sure Search is working, search for "frostwire" under Application search (make sure the floppy icon is showing left of the search form, touch whatever icon is showing to change the search type)
When you send a search, that search message will be received by most of your immediate peers, they will search themselves and forward the search message to their peers, and so on. All search results will be forwarded back by your peers to you.
If you get no search results, it's for 2 reasons:
1. You have no peers to send a search
2. The search term yielded no search results from anybody.
Make sure you've selected the correct search type.
Here's a video on how to search, browse, filter results and download.
http://www.youtube.com/watch?v=yNB0chaZ-F4Hope this helps.