Contact relevant blogs (up to you to find which ones) and offer them a reason to post about it.
A guy created an iphone app that was relevant to my website users, contacted me offering a few free downloads for my readers. I made an article about it (because I thought the app was cool) and then went around forums/reddit etc telling people the first 5 who would comment on that post would get the app for free.
It's a large numbers game... from my blog maybe 1,000 people read the article and of those maybe 20 bought the app.. but the ones who bought it probably recommended it to their friends etc..
contact 50 blogs, it's time better spent than twitting IMHO
Point well made. I'll see if I'm able to contact blogs and see if they would be interested in writing an article about it when the beta's out. I'll offer early testing of the beta so if they do decide to talk about it, they can. I'll start gathering a list. Thank you for the great feedback- very helpful! What's your blog about? Any links?