Most app developers who want to get noticed fill a niche that isn't being currently filled by another app or they come out with an app that greatly improves the user experience. All it takes is a few people to be pleased with your app and rec. to friends, then it mushrooms - then once you get publicity on forums like this and in Android blogs, you've hit the big time.
Edited to add: A nice website and press release about your app is also very necessary.