What I found to be the most helpful was trial by fire. I dual booted Linux and Windows for a couple of weeks when I first started. I found that I would get confused about how to do something under Linux and would just switch to Windows. I wasn't getting anywhere, so I just removed Windows and forced myself to use Linux only. I needed a tablet and phone around to search wikis and read forums and all that, because I would break things all the time, but I learned a lot that way. I started off with Ubuntu and tried to use the terminal for as much as I could handle, then I moved to a more involved distro (Arch).
Regardless of what distribution you choose to go with, I would highly recommend Arch/Gentoo/Slackware if you are trying to learn about Linux (after an intro in an easier distro), because you are forced to set up everything manually, and learn what happens behind the scenes in Ubuntu, Mint, OpenSuse and the like.
In addition to this, if you do prefer the book style learning to the getting your hands dirty style O'Reilly has some good books on Linux.