Depends on your product, I guess? For me, it's usually: make a splash page, make sure your assets (app icon, screenshots, trailers) are eye-catching and professional, write about different aspects of your product on your blog, condense your pitch down to a paragraph at most, e-mail every publication you can think of (and follow up), post in lots of topical forums and comment sections (esp. HN and subreddits), submit your product to publications that give out awards, try as much as possible to catch the eye of Apple's promo team if you're in the app business... but, caveat emptor, I'm also not great at it yet. It's a hard job.