I don't remember how I taught myself programming... probably a good thing, since I almost certainly did it completely ass-backwards. Here are the blundier blunders I wish I could undo:
1) Learn the science ASAP. It's not hard to get a list of the important algos and data structures, and look them up on Wikipedia. Implementing them in the language of your choice is good practice.
"Practice makes permanent, but perfect practice makes perfect." The sooner you grok the science, the less time you'll spend writing bad code. Ideally.
2) Get involved in FOSS. Writing documentation is a good place to start because it requires you to read someone else's code, and understand what it does. On top of that, it gives you a chance to network and learn from more experienced developers.
If you're going to be involved in FOSS, then learning some sourcecode management systems is essential. The learning curve tends to be steep at first, but even if you only want to work on personal projects, you'll be glad to have access to the project at earlier points in its development. Learning the GNU tools— grep, sed, awk, diff, etc— are great for productivity and go hand in hand with SCM.
For Lisp in particular, I'm enjoying Paul Graham's
On Lisp. I'd already read halfway through Peter Seibel's
Practical Common Lisp, and they're both good books, but On Lisp was the one that got me
excited about this language, and rekindled my mania for programming. In fact, this:
eble wrote:All of a sudden, I got overwhelmed by....I'm not sure....I just couldn't wrap my mind around some of the implications.
...happened for me around chapter 6.

"If you want to improve, be content to be thought foolish and stupid." -Epictetus