Let's take a look at the difference between how a web search engine, such as Google, serves relevant search results compared to the iTunes store. There is an interesting tradeoff happening.
Google indexes such a colossal amount of web pages that the potential results can not possibly be human curated. Google has to rely on algorithmically detecting bad results and filtering them out.
Apple has to deal with only around 700,000 apps, and every app has to undergo a review process in which all the content that the user will ever see will be looked over by a real human.
As such, Apple does not have to worry about 'bad' content showing up in searches, unless a developer hides malicious code in a clever way. Even then, the app icons, names, descriptions and pictures are all curated. Google, on the other hand, has to deal with everything the Internet can possibly throw at them, and so relies heavily on a lot of statistical rules and machine learning to filter out malicious content.
Google has to index pages submitted by people all over the world that it has no business relations with, and can at best rely on looking at information such as whois data, ip addresses and other information to figure out the ownership of websites.
Apple has the credit card information, billing address, phone number, real names and all other kinds of information about developers that submit apps to them. Developers can be held responsible for their content, and the barrier of entry requires higher technical skills -- one must own a OSX device, install xcode, etc.
Once again Google has to rely on much more complicated algorithms to serve relevant results because they simply can not trust the content on the web pages. Google has developed very complicated tools to understand the intent of a web page, analyze the relevancy and category and figure out if a web page is relevant to a result, etc.
Apple places a lot of trust in the App developer, it's up to the developer to figure out what their app is relevant to. Therefore, more of the responsibility for App Store discovery is in the hands of the app developer. This is a reasonable assumption only because apps are reviewed and any underhanded tactics will be caught, and the developer risks losing their $99 fee.
Google indexes a large amount of pages on an individual site, so a very large site such as cnn.com may have tens of thousands of pages, each indexed and showing up in search results for a net total of an immense amount of search terms.
Apple only gives apps 100 characters worth of space to select keywords, so even an extremely popular app such as Angry Birds is limited in scope on what keywords it can show up for. Companies can make different versions of their game with slightly different keywords, but nothing will ever come close to the amount of terms a large site can have.