Beginning Python
Beginning Python is a revamped edition of Practical Python. What's so different? It's got some re-wording, re-formatting, and about, oh, seven new chapters. Is the new edition worth it? Definitely.
This book is a great learning course for Python. If you're completely new to programming and basic programming concepts (like variables and conditionals), you'll have to start somewhere else. However, if you've got a language or two under your belt from some class you took in High School, you'll do just fine. The core basics that no one ever likes to read are all covered in one simple chapter. After that, it's all about what makes Python so great.
The best part about this book are the programming projects at the end. Where any other programming book will leave you wondering what to do with your newly acquired knowledge, Magnus jumps into ten different projects. Anything from making an arcade game to generating markup. The projects on making your own file sharing program out of XMLRPC blew my mind when I first read them in Practical Python.
Overall, this is a great book. I gave Practical Python an 8 out of 10, but the new edition definitely gets a 10/10. It has everything you need to get a great start with Python. After you read this, I'd still recommend picking up the Python Cookbook and Python in a Nutshell for reference and Dive into Python for some advanced concepts.
You can find more information about the author, Magnus Lie Hetland, at his home page. The technical reviewer, Jeremy Jones, writes Python related stuff over at O'Reilly.