People sometimes ask me to recommend a book for learning to program, or a book on Python. If you want both in one book -- to learn Python as a first programming language -- take a look at Allen Downey’s new book Think Python.
If you’re an experienced programmer and just want a book on the specifics of Python, I’d recommend David Beazley’s Python Essential Reference.
These two books are at opposite ends of the scale. Downey’s book is a very gentle introduction to programming. He takes the time to explain things that authors often don’t realize need to be explained. Beazley's Python Essential Reference is all about Python, not programming essentials. The title says “reference,” and it does make a good reference, but you could sit down and read through the first half of the book. The second half is really more of a reference.