I've been told a good independent book publicist (i.e., working outside the publishing house) will set an author back $9,000-15,000. I opted not to go that route.
Presumably there are cheaper options. I get many, many, many press releases from publicists promoting self-published books. Some produce polished copy; others offer incoherent releases full of typos. Some personalize; others (many) spam. In general, I would say that if you can write a good, concise blurb for your book and research media outlets online, these people aren't doing anything you can't do yourself.
Fact is, most media outlets will not cover you without a strong local angle, because they are inundated with press releases about books. I don't count, but I would guess I get 20 to 50 per day.