Viaweb's PR firm is discussed in the fourth paragraph here: http://www.paulgraham.com/submarine.html
We didn't do much better, because we were also repped by a PR company, and playing the same pasteurized process press food strategy as the rest of them.
Which is my point. Wasting money on a jaded middleman to circulate press releases every time you make a dot release isn't something you should aspire to do when you can afford it, and PR isn't something you should avoid doing now.
My current company, a tiny startup, is in Forbes, Wired, EWeek, Network Computing, Inforworld, Baseline, not to mention Slashdot, Digg, and Reddit. Didn't spend a dime to do it. Definitely got lucky, but there's also definitely a trick to doing it.
I agree with the "survey" trick Graham talks about. I've seen that work over and over again.
What I see work, over and over again, is companies manufacturing surveys or studies that come up with numbers and metrics about the market, like, "20,000 enterprises are deploying technology to stop the Storm worm". Some companies will do annual press releases about an official-sounding report they generate, like, "Weboopia's 5th Annual Twitter Study Concludes 4,897,489,281 Messages Delivered Over Twitter In 2007".