We used to browse Yahoo to discover cool websites. 15 years later we browsed apps stores in the same way. Neither scaled very well.
Of course, this didn't scale once the web started taking off. You can't browse through a catalogue with millions of entries. Equally, with over 900k apps on the iOS app store and almost as many on Google Play, browsing there has also become meaningless. Browsing an app store is like browsing Amazon - you could spend the rest of the year clicking 'next item' and not see that one cool thing you really want but didn't know existed.
After the web directory the next stage was the 'portal' - a page with someone's ideas of what might be useful. This is what Yahoo became, and it's also what the front page of the iOS or Android app stores look like now. The purpose of these screens is not to allow people to discover your app or service - they cannot hope to be comprehensive in that way. The front pages of an app store do not exist to help developers - they can't. Rather, they exist to help the users - to ease them into the idea of apps. But they can only scratch the surface of 'discovery'.
All of this means that saying "we made an app and no-one downloaded it, and Apple didn't help" is like saying "we made a website and no-one came, and Google didn't help" or, even more, "I wrote a book and no-one bought it, and Amazon didn't help". Amazon might help - it might feature you, just as Apple might. But that's for the users' benefit, not yours, and it cannot possibly scale to all apps or all books.
The difference between Yahoo and app stores, of course, is that web search came along and addressed some of the underlying tasks in a quite different way, but search does not necessarily work well for apps. Search requires you to know roughly what you're looking for, but a lot of the best apps (and indeed web sites) are things you hadn't imagined could be possible - they're 'magic wands'. If you didn't know Hailo or Evernote were possible you wouldn't search for them - and yet the app store home page cannot possibly showcase all such things.
The obvious answer, of course, is self-promotion - you promote your app like you would your website or your book.
But there are some other more interesting things also going on in discovery.
The first trend is the way that Siri and Google Now surface information. If you ask Siri for sports scores or restaurants or films, you don't need to work out what the best service or app to use might be - you just ask the question (and Apple's BD team has picked one). Google Now takes this a step further - it it also knows the sports score, but it tries to work out new things you might be interested in unprompted - it reads your email, knows you're interested in a flight and pops up to tell you it's running late. As they develop, these concepts may work well for the discovery of some kinds of apps, but neither approach scales well across thousands of apps. And neither would tell you about a 'magic wand'.
The other trend, though, is social. I don't really mean social recommendation aggregators, which work on the basis "people who liked this also liked'. Rather, plain vanilla sharing. Twitter cards let you share an app directly, but also deep link to content within one.
Many of the emerging mobile social messaging apps are trying to turn themselves into platforms, and they have hundreds of millions of users. A little piece of atomised content, a card, the size of a smartphone screen, embedded into a message, is a great way for knowledge of a service to spread (I wrote a little more about this angle here). Meanwhile, the grandpa of social networks, Facebook, is pushing hard to build a mobile app distribution business. Kik, of course, has just launched a Zynga game built in HTML5 within the messaging app itself.
Even more interesting, though, are some of the APIs inside iOS7. Apple has built a local, zero-configuration wireless sharing tool kit. No access point and no NFC needed - any app can reach out and find any other iOS device.
Apple surfaces this in the new system service Airdrop, shown above. The demo uses photos, but Airdrop is part of the standard sharing panel that any app can use, and (without breaking the NDA) it looks like anything you can make into a file could be sent. So an app can include a 'share this with friends' that sends people in the room an app store link. Or a game level. Or in-game currency. Or a deep-link to content within an app. That makes app discovery work quite differently.
Airdrop, though, only works with people in the same room, and so has a different set of scaling problems. The leading social messaging apps all have hundreds of millions of users, and I've lost count of how many such services there are in total - I found over 50 on Google Play that had over 1m reported downloads, and there are dozens more. Pretty soon there'll be more messaging apps than ad-tech companies - a new bubble is inflating. But there might be a fair bit of value for those that can turn themselves into distribution and discovery channels.