If you are releasing a real press release, hoping to gain local media attention, AP, etc., spend the money for a release at
Press Release Distribution Online - PRWeb.. And spend the $300 to $500 to get on the top of the page on the day you release it.. (Tuesday and Wednesday tend to get the best results)..
If you are doing it just for the links and the search engine bump, use
Press Release Service and Distribution - 24-7PressRelease.com and go for the $89 option.. You can get by with the $49 option, but the $89 is worth the extra $40..
There are also a ton of free press release sites, but when you compare the amount of time you spend submitting to all of them vs the cost of using one of the majors, I find it better to just spend the money..