[jesseditson]

Probably depends on the kind of app it is. (I think we're assuming iPhone?) I'd say to start, make sure people can share it on fb and twitter everywhere possible. Then, share it yourself, spam your friends, write blog posts about it, contact bloggers and get people to write about it. If all else fails, spend some money, but hopefully it shouldn't come to that.

[geuis]

Its a website, but does have potential as a mobile app at some point.

[jesseditson]

Well, I tried to make my answer as platform-agnostic as possible, but in that case, I'd work on the SEO to drive some serp traffic in, and maybe use those adwords coupons you have lying around to promote a landing page with prominently placed share links. You'll get a lot of mileage out of facebook links.