There are a bunch of paid ways to promote an app, but I've focused on what I usually do to get free exposure:

1) Post a 'Ask HN' post to get some feedback

2) Search for blogs that discuss the problem your product solves, then comment on those blogs (don't spam!)

3) Email the tip lines of each of the major tech blogs

4) Submit your site for inclusion in site directories (e.g. webapplist)

5) Contact sites that rank highly on your target keywords and see if they'll link to your site

6) Search Twitter for people who have the problem that your product solves, then refer them to your app

7) Post updates to your personal Facebook / Twitter