I developed a short-lived minor hit game several years ago which topped out at #3 on the U.S. App Store overall free chart, right behind the Facebook app. At the time that represented about 50-60,000 downloads a day; I assume it would be considerably more now.

That app was languishing in the nether regions of the App Store until we got press on some Gawker properties at which point it absolutely exploded. It was then picked up by other outlets which only helped.

There's a million apps out there and media outlets are not going to talk about all of them, so the way we got that press was by making writing an article about us more valuable to them: we gave them something to give their readers. This was a $0.99 app (these were the days before it was clear that charging money up front for apps is not a viable strategy). We scheduled a weekend giveaway about a week out, emailed media about it, and they got to offer their readers more than just pointing out an app they might like, they got to give them a deal on it.

So, in my limited experience, a good way to get traction is through some combination the media (they have the eyeballs) and a deal (people love deals). And the best way to get the media to talk about you is to make talking about you more valuable to them.