I rely a lot on the top 100/200. I usually only pay attention to the top paid ones. I heard about a few apps through word of mouth, Beejive for example. Wouldn't have paid $10 for it if my friend didn't praise it so much.
Personally, I like to search the app store. I get an idea in my mind of an app I'd like, then I search and hope it exists One time I searched for "Colour/Color Identifier" and found an app that actually did what I was hoping for. It used the camera to identify colour's names (and provide hex codes) in realtime.
It really helps to just search for keywords, as you'll find apps you never knew existed. Half of these amazing apps don't even have any reviews. Sometimes it's worth taking the risk and trying out these apps.