It depends on your preferences. I learned by reading Magnus Lie Hetland's Beginning Python: From Novice to Professional (Apress) many years ago and also used the How to think like a computer scientist link above. I hate video tutorials. I hate having to wait for them and not being able to skim, I hate that they require more focus than reading, and just generally prefer other methods of learning.
After I got a solid foundation from the two sources above, I learned way more on this very forum than I probably could have otherwise.
Just reading won't help entirely though. You have to find something you like, and write programs. The more you code, the more you'll learn. I have a dozen half-finished programs on my computer, but even though I didn't finish them, I learned a great deal from each of them. If you're creative enough to find ways to enjoy programming, you'll be able to learn it much easier than someone with no creativity who's good at something like algorithmic math (everything up through Calculus in high school for me).
Join the #python-forum IRC channel on irc.freenode.net!