Alright, so you’ve written a book. You have an agent and a publicist. What are their jobs? What’s the difference between the two?
An agent submits your manuscript to publishers. (This isn’t some lightweight thing; not only do few publishers read ANY manuscripts not sent in by agents, but the agent also maintains regular relationships with a number of publishers so that she has an idea of what they are looking for at particular times, etc., and can gauge which house is the best fit.) She also negotiates the deals, vets and negotiates the contracts, and accepts advances and royalty payments from publishers on your behalf. She may also try to sell other rights for you, such as foreign market translations, etc., and deal with some of the tax problems those impose.
Your publicist is the one who tries to get people to know about your book (once it’s with a publisher). She may do any of the following: Arrange bookstore appearances/speaking engagements/school visits; contact magazines, newspapers, TV & Radio, and other media outlets to try to get your book reviewed/featured or you interviewed; go to conferences and trade shows and try to meet with book buyers (for institutions/retailers, not individuals—i.e., people who decide whether B&N or a state library system will purchase your books or not). Some of these latter tasks may be taken up by sales staff at the publisher. In fact, you probably will have a publicist at the publishing house who may do some/all of the above.
I was always kinda confused about this, too, until I started watching “Entourage.” Watch an episode from the 1st season, when they’re all just starting out in Hollywood.
Ari Gold is the agent. Shauna is the publicist. Both of them work their tails off for Vince, but in very different capacities. For example, Ari lands a new movie deal, and Shauna sets up the interviews to promote it.
And don’t forget Eric is the manager. It’s amazing Vince ever has any money left at the end of a shoot.
Authors don’t have publicists unless they’re on the Times best seller list (and often not then).
Most publicists are scammers. That doesn’t mean there aren’t any legitimate ones, but legitimate ones only represent firmly established authors – multiple best selling books.
Agents are different; nearly all published authors have agents these days. But a publicist is a waste of money for 99% of all authors.
In a nutshell, your agent works for you, representing you, negotiating on your behalf. The publicist works for the publishing company, handling that particular book. Personally, I don’t have an agent (I represent myself), but I have written books for several different publishers. Each one handles only the book(s) I wrote for that publisher.
Your agent’s work is primarily done before the book is published (in the nonfiction world, they often start before the book is even written. They’ll assist in getting the book placed with a publisher, and in negotiating the contract.
The publicist’s job begins once the contracts are all signed and the printing dates are set. They’ll work on getting out press releases, sending review copies to publications and buyers, setting up author events, writing back-cover copy (sometimes), negotiating placement in catalogs, negotiating co-op marketing deals, buying ad placements, and anything else that involves the actual marketing of your book. Or, when you deal with a very small press, the publicist makes you a little poster and sends you off to book your own author events 
I didn’t see this until I had already submitted my response.
I would say that most authors who have an agent will end up with a publicity budget negotiated into the contract (small though it may be), and the publisher will provide a publisher who spends that budget.
Publicists that work directly for the author are completely different animals. I have never employed my own publicist, and when I’m contacted by the direct author representatives at my bookstore or newspaper, I frequently find them clueless.
Part of what distinguishes a good publicist is knowing who not to call. It is an utter waste of time and money to contact bookstores in Montana to sell a restaurant guide for Miami. We’re not going to stock it. Yet I get calls (and press releases, and emails, and…) for books like that all the time.
Quick caveat about the word: Prior to around 1970, you may see what has become largely an outmoded usage that was the original and dominant one in the earlier part of the century: “a writer or commentator on public affairs, especially on international affairs and law.” The person whose job it was to promote his principal’s publicity and public relations was a “PR man” (PR for public relations, of course). The use of “publicist” for this vocation began in the 50s in a few trendy publications, and grew to displace the original meaning by the Watergate eriod. The work of celebrity columnists like Walter Winchell and Louella Parsons tended to blur the distinctions, but seeing someone like Walter Lippmann described as a “publicist” in writings of the time might give entirely the wrong picture of his role to someone today.
I’ve never seen a publicity budget included in a book contract. It’s up to the publisher to determine how to promote the book and that’s never part of the contract.
Publishers use salespeople to get the book into bookstores. They do have a promotion budget, but that’s an internal amount that author has no say about.
Authors can hire publicists, but I know of none that do. In general, you can be just as effective yourself by simply contacting local newspapers and radio. As far as getting books into bookstores, it’s the publisher that does that, not the publicist, for the reasons you point out. The “publicists” you see are clueless because they have no stake in getting the book in the bookstore, anyway: they’re probably charging someone by the number of bookstores they contact or some such.
Not only have I never seen a publicity budget clause, but the literal publicity budget for the vast majority of books is exactly zero. Other than inclusion in the publisher’s catalog, most books get no publicity at all of any kind. And I’m using publicity in the largest possible sense, including all marketing, promotion, advertising, and dispersal other than sending out review copies.
If anyone in this thread lives in a world different from this, please let me know where it is so I can join you. 
While I have never managed to get a publicity budget into any on my contracts, I have absolutely seen it done. A nature writer friend of mine had both a dollar figure for publicity and placement in the publisher’s catalog negotiated into his last contract.
I have gotten specific publicity items in my contracts, though, like promotional mailings.
I AM PUBLICIST! (Seriously)
It would be my job to get your book into the public awareness, thereby increasing demand for it. That might mean booking you on a talk show or a bookstore signing, approaching the news media to interview you (particularly if it’s a non-fiction book), talking your local newspaper to run a feature story on you, hooking you up with various events that will expose your book to a bigger audience, etc.
I don’t find you a publisher, get your book evaluted, negotiate your publishing contract or handle what happens if a movie studio wants to turn your book into a film.
That’s not so much the problem as new authors who expect Stephen King-level publicity for a drugstore novel, and the publicist who charges by the hour.