The official python tutorials are pretty good actually:

http://docs.python.org/tutorial/

I've heard good things about Zed Shaw's new book http://learnpythonthehardway.org/

I've also heard great things about Allen Downey's books on Python, but I am not sure which one is best to start with.

Core Python Programming (2nd Edition) by Wesley Chun (http://python.net/crew/wesc/cpp/) is very good. It's somewhat dated now, but is very readable.

Once you've learned the language, David Beazley's Python Essential Reference (4th Edition) (http://www.dabeaz.com/per.html) is excellent.

learnpythonthehardway.com is good. I'd also recommend Think Python at http://www.greenteapress.com/thinkpython/thinkpython.html

http://diveintopython.org/ is a good python intro that assumes you already know how to program in some other language.