Their search on the Google Play store isn't that great, though they now have a feature where what they auto-suggest when typing your query is usually what you want (for larger apps like netflix, ebay, etc)
The only problem I have is when I search for something that isn't there. Happens sometimes that what I want simply doesn't exist in their store (like, for example, VLC), and when that happens all of the near-hits come up. If I am thinking about it, that is the correct behavior, but it still strikes me as strange every time it happens. I think the reason for this is that I have become spoiled by usually only searching on the web, and when I search on the web it is very rare that I don't get any desirable results at all. Google's web search has spoiled me.