We just started a google ad campaign for Imangi. There is a thread in the promotions section of this forum where other people have also posted more ideas.
I wrote up a blog post on marketing your iPhone app. In addition to what I wrote at the beginning of the year I should add these ideas:
- using the promotion codes to have bloggers write reviews for you
- consider using AdMob for advertising since the ads are served right on the iPhone itself