Forum Moderators: open
It depends on the nature of your site and it's audience. I try to sort the most efficient means according to the promotion budget available. Both online and offline, targeted promotion works best.
A lot of interesting threads are available in this forum's library [webmasterworld.com]. Have a peek in there, it's worth it.
Im sure you could find a good site that advises on writing a press release.
Maybe you dont want to inform BBC and CNN of your site, but some trade magazines or local news agencies may be interested.
Most trade magazines have online versions and usually accept contributions (news items, articles, etc) which would be a good way of reaching a specific market.
If your site sells a product in a regional area you could offer one as a prize for a competition on local radio.
Its difficult to come up with ideas without knowing the specifics about your site. Without going into detail, what kind of site is it? Product / service, local / regional / national / international, mass market / niche market?
JOAT :)