If you're announcing something of sufficient interest so that quality sites are inspired to pick up the story, online PR (public relations) can indeed be worthwhile.
The most important factor to assess is whether the news release service has credibility with the kinds of folks that you'd like to have writing about your site. If something has a spammy aura to you, trust your instincts and look elsewhere.
Some news release services will let you include links within the story, some won't, and for some that's a paid option. Some services will put their own redirects on any links you include. Be sure you understand what you're getting, but don't let links be the make-or-break factor in your decision about where to issue your news release.
Direct links in a press release can be useful for SEO, but only if other sites pick up the story. Go after credible exposure first, and links second. Quality journalists will often rewrite a news release to adapt it to their own contexts. It's not uncommon for a link or two to be added by the journalists who pick up the story.
Like buckworks said you have to say something interesting. When doing a press release it needs to be news. Come up with some interesting data. Journalists love charts and studies. If your business generates a lot of data mine it to come up with interesting statistics. PR's have to be interesting.
note that some of the "free" PR sites will embed text link ads and surround your PR with contextual advertising that may be directly competitive to your product or service or antithetical to your message. in other words your PR is simply fresh meat for their MFA-type site.
Best promotion is what you can do yourself. That way you have complete control of the roll out. I'd be wary of sites that offer roll out/linking as they would have a commercial axe to grind, and will be grinding it before yours ever gets to the whetstone.