I'd still like some actual recommendations for a good book for beginners.
My "PHP and MySQL for Dynamic Web Sites: Visual QuickPro Guide" has already been mentioned by someone and gets good reviews. If you want something more basic, I wrote "PHP for the World Wide Web: Visual QuickStart Guide" for the non-programmer. It goes at a much slower pace but obviously doesn't cover as much. Although neither is technically a textbook, both are used as textbooks in high school and college classes.
For a recommendation without the self-interest, the Thomson and Welling "PHP and MySQL <something something something>" (Sams) is a very good book (I forget the title, but it is good and thorough).
Whatever you look at, make sure you get the latest editions. I know that Amazon doesn't necessarily offer up the latest edition of a book, so you sometimes need to click on "All Editions" to see if it's been updated.
Hope that helps,
Larry