I also have a start up working on our first product launch in a few short months. I have asked the same question to friends who have gone through this before and most of the time I am getting the same answers:
Start your own company Blog and start creating content relevant to your industry immediately (even if your still unsure when your product will launch).
Find the "online watering holes" or forums where your potential customers hang out and start joining in on the conversation. Sooner or later you will start getting noticed.
Get your website with blog up and running asap, even if you are not ready to sell. This will help alot with SEO, because you will be able to create more backlinks to your site.
(This can be extremely valuable). Make a list of the top bloggers in your industry, subscribe to their RSS feeds and post relevant and interesting comments on each new blog post (try to be in the first 10 comments each time to make sure the blogger notices you). When the time is right, e-mail them directly asking them to review your product for their blog (sincerely).
Remember: Getting 5 bloggers each with 1,000 followers to review your product can send 5,000 targeted visitors to your site, costing nothing but your time. How much will 5,000 PPC's cost you?
You'll notice that most of the advice costs nothing (except if you need to hire a web designer). And its the advice i'll be following for my product launch.
Best of luck!