I didn't really like Learning Perl; I came to Perl with a fair bit of programming experience, and LP put me to sleep through the first half-dozen chapters. I'd go with Programming Perl to start with, especially if you've got previous experience in programming. I'd also suggest The Perl Cookbook: it's a great place to pick up Perl idioms, and a pretty good resource if you need to get something done, but don't have the time (or patience :-) to figure it out from first principles.

I also like Mastering Regular Expressions. It really does a good job of demystifying regexes. I read it cover to cover in one sitting. (Yeah, I'm a geek.)