Here are some suggestions:
1 - Hire a Marketing Consultant to help you come up with a marketing plan.
A consultant with experience in marketing can help you formulate a plan to get your product out to your target market. They can also help you determine who your target market is.
2 - Use social networking.
Many new software products are marketed through Twitter, Facebook, Google Plus, and other networks. Create a Twitter account with your product name and also create a Facebook page for your product.
3 - Build a website.
I assume this goes without saying, but I put it here for reference just in case it's not obvious. However, what might not be obvious is that you probably shouldn't try to do this yourself. People do better at what they specialize in, and building a great website involves a great content writer, a great web designer, and a great front-end coder. Most of us can not do all 3 -professionally-. Note the emphasis on the word "professionally".
Having a good website is key to making your product look like it has social proof and is not something someone slapped together in their basement :)
4 - Advertise on Google
Advertising on Google using Adwords can help drive traffic to your new website.
5 - Blog
Content is king. The highest ranking websites tend to be those with the most relevant content, and blogging is a great way to build content for your site. Use Wordpress or Blogger to create a blog for free. You can also have your web design consultant build a design for the blog too so it matches your product and website branding!