+1 to Learn Python the Hard Way website. The hard way being you actually have to program, instead of just reading a bit. Programming is easy, I've been doing it since I was 7 or 8. The hard part is finding your bugs
After you have done some tutorial bits, just think of something small you want to do in Python, then think on how you can split that up in a few main tasks and start writing. Use Google for examples. Make mistakes, get stuck, it is all fine as long as you continue programming. As an analogy, you can learn to play an instrument without a book or instructor, as long as you practice, practice, practice. You can't learn to play an instrument from a book or instructor without practicing. Programming is just as much an art; practice and don't be afraid to make some false notes early on
I always keep the Python documentation open in a browser; you can really learn a lot from there also (once you understand some programming concepts). http://docs.python.org/py3k/
As an example of a small project you could do (or something similar), to get started with Python I wrote a reminder program, that reminds me of recurring events like birthdays and such a few days in advance. I'm horrible at remembering things like that, so it sounded like something useful for me and small enough to not get lost in complexity. The completed program is just 60 lines long, reads the dates from a file where recurrence can be either monthly or yearly and it has some special cases for things like summertime and wintertime (last sunday of a month), it is configurable per date how many days in advance it should remind me and it uses the zenity command easily display the message in a friendly way (would probably use libnotify today).
Keep it small for your early projects. And make frequent backups of your code, either using a version control like Subversion or something similar, or by just making a copy of your files. You will find one day you break something, and you can't recall how the code was yesterday when everything still worked