I started learning Perl on Win98, because VisualBasic just hurt too much. My only previous programming experience had been Basic and Machine Code on an Apple IIe. I stumbled across Perl and fell in love.
I agree with FunkyMonk that projects are a good way to go. Most of my learning has come from working on personal projects, things that I wanted to do and that were fun. I would keep trying until I got whatever it was to work. Given my programming background, this involved a lot of unlearning wrong ways of thinking and frustration to begin with.
One of my favorite books is Perl Hacks. I also use web searches and am starting to learn just how awesome perldoc can be.