Display ads - waste of money. The return on banner/text ads is very disappointing. Google has the best CTR. Facebook are well-targeted, but are expensive (if your app sells at less than €3, then it might not be worth your while). BuySellAdsallow you to purchase ad-space on some popular blogs - the service itself is great, but sites I've advertised on didn't give a good CTR.
Journalists - big blogs (Techcrunch, etc) are worth contacting but don't expect to get featured, unless you're VC backed and have raised a bunch of money. Focus on smaller, niche blogs - for example, a Russian iOS blog caught wind of a Muud.io sale and subsequently sales spiked 400% for couple of days. Local journos are usually eager to help out too.
App review sites - a handful of the bigger ones are worth contacting. A personal email works best if possible - press releases are usually ignored. Most are a waste of a promo code however.
Apple - extremely difficult to get noticed. Build a great app and you've a better chance, but don't count on getting featured. If you have any contacts in Apple, it's worth getting in touch - you might at least get your app in front of the iTunes editorial team for review (even so, you're still not guaranteed placement).
Twitter, Facebook, Google+ - Worth maintaining a presence. The more active you are the better. Twitter is #1 referral stream for visitors to the Muud.io website.