Your strategy is going to depend on your target audience. If you are making a game like Angry Birds then you will probably use a different strategy then if you are doing something like business type apps: Evernote, Dropbox, Omnigraffle.
You market to people so it's critical to know who those people are.
Some ideas:
- Find people discussing similar apps on Twitter using Tweetdeck or Hootsuite
- Submit your application to tons of app review websites
- Submit press releases to relevant industry websites (where your target market would go)
- Contact key business Associations, business groups, or hobby groups that could use your app
- Give away free copies, run a sweepstakes, or some sort of online buzz generating activity
- Find people who follow competing or similar applications and market to them
- Build an amazing product and people will promote it for you
But your strategy is going to depend a lot of your product.