This is a very important point. I've got an incredibly simple app on the market, but because of some good publicity, it's gotten some good download numbers. On the flip side, I'll see great apps that've gotten < 1000 downloads simply because the author didn't get out there and write to every blog in sight.
I just threw email darts at the dartboard that is Android blogs. A few of them stuck, and people started to download. That got me some decent ratings, and it's kept going from there.
As I said in another comment, emailing Android blogs got me a couple of app of the day type things. I also stumbled across my app being the top comment in a fairly popular Reddit thread which I responded to (as the developer) which got me a spike of good ratings and activity. To be quite honest, it was a fair amount of luck.