Submit to the good directories. Killer Startups, FeedMyApp, and probably a few more I can't remember. They'll give you a few hundred visitors for relatively little effort.
Get involved with local events. Things like demos and barcamps can be quite valuable. Doesn't matter how small - someone is listening and might write about it. Plus, you get some solid feedback and possibly a lead or two.
Use AdWords if you can make the math work.
If you have a market that will oblige, cold calling bloggers will get some links. This is tough with technical products, but can be very productive with a less web-savvy audience. (If someone knows how to get tech/development blogs to pay attention, please let me know - we're a tough nut to crack).
If you want to hit the BIG blogs/media outlets, hire a good PR guy with connections to those blogs. It does work, but costs a fortune.
SEOMoz and Hubspot (among others) have some pretty nice SEO tools that will help drive the content you need to write and the links you need to target. Expect a multi-thousand dollar investment here, though.
Find trade groups and tell their members about your product.
Then you just do it over and over. Think opportunistically, and be patient. Just before it starts working, you will probably want to quit. Don't.