I've recommended Cal's self-paced online study guides
http://www-inst.eecs.berkeley.edu/~selfpace/cs9honline/ to good feedback for an introduction to python and programming in general, while myself mostly relying on the books by Alex Martelli (Python in a Nutshell and Python Cookbook)
Two things: lots of risk and the O'Reilly book, "Learning Python."
I work for a company and was running a research project in air traffic control worth ~$400K. I was the principal investigator. We were going to create a tool that would redesign the airspace boundaries managed by a controller or controller team. At the time, I programmed in C, Awk, and a little Perl. I'd used Python at the command line, but had never programmed in it. I knew however it was the language we needed. I committed to it, and my partner agreed to it. We both learned Python on our own and the project succeeded. It had to succeed. If it didn't, we were in lots of trouble. We had company VPs watching us.
The Learning Python book is superior to the Programming Python book. While both are written with the same author, the Learning book is far more readable.
My favorite ongoing resource today is the documentation that comes with Python. I have a copy of it installed on the Linux box at work, and on my Macs at home. It is hands-down the best quick reference for the language.
With a healthy amount of coding, I've gotten very comfortable with python, although I still feel like I'm not quite utilizing it idiomatically. As such, I've been going through Programming Python ( http://oreilly.com/catalog/9780596009250/ ) - which is very well written, IMO - as well as reading a healthy amount of other people's source code, notably CherryPy ( http://cherrypy.org/ ), since I use it a lot.
If you're experienced with other languages, I'd suggest implementing something like a tetris clone as an exercise in learning the language. If you're only experienced with web-dev (as is often the case these days), I'd recommend implementing a few small web-apps with CherryPy - it's the most "pythonic" "web framework" I've seen so far.
I pretty much begin doing projects in it. Started with some basic web scrapers, then I built a site in Django. Yes, I was one of those bastards that was learning Python AND Django at the same time, but it worked out for me.
I read the Python tutorial, and I have Python in a nutshell which I find is a great way to look something up and get a pretty good, detailed explanation on it.
I'll second the python challenge. Unlike Project Euler, this challenge required the participant to rely on finding and using some python libraries (for imaging, networking, compression, etc.) to solve the puzzles. So, not only are you researching the language to figure it out, but you're actively engaged in self-directed research to find out how to complete real tasks with python.
I've also read the "Dive Into Python" book, but that was equivalent to reading a book about an instrument without actually holding or playing one.
I'm always in the middle of learning a new language or framework, and the general pattern is always the same:
Read a bunch, get a project idea, start hacking on it to practice "muscle memory", use reference documentation a lot, go back and re-read -- picking up lots of info you missed the first time, get back to hacking. Keep cycling.
Many moons ago, I distinctly remember reading the 'Programming Perl' book 7 times before I finally felt like I understood what I was doing.
Thing with Python is that it combines a shallow learning curve with very quick payback. You can use it as a glorified shell script if you want, and very quickly get something useful done, then anything you learn will have an immediate application to your next project. That's how I got into it. Then you go back and realize, hey, this for loop would be better as a list comprehension, these functions would work better together if I put them in a class, and refine your code.
I bought Beginning Python from APress, read through it in a day or two, then just started hacking. From then on the only things I used were the official Python library reference and any existing code I happened to be hacking on. Occasionally I'd look up articles on the Web about something I wanted to learn more about (decorators, meta-classes, etc.)
Actually I used "the" tutorial at python.org. But simultaneously I dived into it by writing web apps (which I was learning as well). In fact I wanted to learn writing webapps (and man there is so much more left aaaaah) and it came down to a choice between ruby and python. I went for python. And no, I am not going into why I chose one over the other!
So I just learnt it by writing several simple apps (thanks to django) and subscribing to a whole bunch of blogs to learn tips and tricks incrementally over time.
Really fun and challenging projects from image and audio processing to network programming. Each level is a computing puzzle which you must solve to progress to the next level. Very helpful forum too, which you will be needing since you'd have no idea about the techniques (the relevant python libraries and such) involved at the start.
I had a job where (among other things) I was teaching Python (and the VPython package) to high schoolers. That made me comfortable with it. Combined with PyLab and a need to wean myself from matlab before graduation, I worked on a few homework projects for other science classes. And most recently, I've been doing project euler.
thinkpython.com - although its supposed to be an introduction to programing using python but it suited me really well, even though I was a C++ programmer for four years. You can skip the basic parts and run through some of the explanations which are for a new programmer but all in all a rapid start guide for python.
The ipython shell (http://ipython.scipy.org/) was great to experiment and learn with, and it's a huge productivity boost every day. It's where I do most of my work. It would be very hard for anyone going back to the plain python shell after trying ipython.