Ask HN: What's the best way to advertise a paid iOS app?

We run a nice little lifestyle business selling paid games on iOS; we've never spent a penny on advertising, so we're thinking of trying it. What's the best way to buy ads for non-free iOS games? What about paid non-game apps?