O'Reilly's Programming Python is not bad, but it's not a great book, either for beginners or journeymen.
Python in a Nutshell is more suitable as reference book, although I suppose you could use it to learn Python. For a Python reference book, I found David Beazley's Python Essential Reference to be more informative and better organized: http://www.amazon.com/Python-Essential-Reference-Developers-...
As other people have mentioned, Guido's online tutorial is pretty good, and you don't really much else to start programming in Python:
I'm always puzzled by people recommending Mark Pilgrim's Dive into Python. I don't find it a good choice for Python beginners.
Fresh book recommendations delivered straight to your inbox every Thursday.