I started out with Sams PHP MySQL Apache All in One. It was okay for the very basics. I have tried several more over the years. Core Web Application Development With PHP and MySQL and Web Database Application with PHP and MySQL (both are not good IMO). Programming PHP seems to best cover the basics. Learning PHP 5 is good but is more of a cookbook.
My favorites are both from Wrox. PHP5, Apache, MYSQL Web Development for the basics and Professional PHP5 for the OOP.
Other good ones are PHP in a Nutshell and PHP Cookbook. Both from Oreilly. Web Database Application with PHP and MySQL is one of the few Oreilly books I haven't liked and I have many.