1. Do not use a PR firm. If you are on HN you are probably a startup with out funding. They will charge you an arm and a leg. You can do better on your own. Be passionate about your product - people will respond more to that, then anything else.
2. Make your product sexy. Sexy sells. A new way of using mobile phones is more interesting than a new DB model. If it is not an inherently sexy product, make sure it looks professional. People want to write about companies that 'feel' professional.
3. Come up with a story. "we are two guys who sold baseballs for 3 years and worked on this in our spare time." "the recession hit, and we both lost our jobs, and this was the result."
4. Reach out to reporters. Every newspaper/magazine/tv news show now lists reporters emails. Reach out to them; tell your story. Find them, and buy them a drink. They are often young and looking for cool stories.
5. Network your face off. Go to places where new startups launch, and launch there. Meet everyone. Get business cards. Tell people you are looking for press contacts. You should be doing this stuff anyway.
6. Use http://www.helpareporter.com/ Journalists need stories to write about. They need new (sexy) material. Craft your story to fit theirs - don't lie, but if you started in a recession and they are talking about new businesses in the recession, make your story fit.
7. Leverage your friends in PR / make friends with people in PR. If you are based in a major city, if you went to college, if you know anyone in marketing - you have a friend or friend of a friend in PR. Leverage them to write Press Releases (which I don't think work in the beginning) and to send you out the emails they get looking for stories.
8. Make an awesome product - at the end of the day, if your product sucks, nothing else you do will matter. No one will write anything about it (unless your FB)
Ok, just a bunch of quick thoughts from a guy who has had a little luck with this.