I would reccomend the book
Beginning PHP and MySQL 5: From Novice to Professional, Second Edition it is by Jason gilmore. its pretty good I also have the book (and refer to it very often

PHP and MySQL Web Development (3rd Edition) (Developer's Library)
the authors are Luke Wellington and Laura Thomson. The book comes with a CD that has the sample scripts from the tutorials in the book which make it easyer to look them over play around with modifying them (to further your knowledge) which I like to do.

Well theirs my two cents for what ever its worth :-)

As a side note you might want to make sure you get books on php5 since php4 will no longer be supported and their is a big push to get people to use at least php5+. Theirs no sense in learning older versions of a programming language that wont be supported by the community any more :-) Just a side not wanted to throw in