First let me warn you that Perl is NOT CGI and Perl is not only for use on the Internet, Perl is probably most commonly used on a local system, not a web server. I recommend that you do not start with any books that have CGI in the title, because that will blind you from what Perl really is. I started with a book called "The Quickstart Guide to Perl/CGI on the World Wide Web." I thought I had a good handle on things until I found PerlMonks and realized that Perl is commonly run from a command line, that Perl and CGI are totally different things, and that the Internet (CGI) doesn't do Perl justice in 19 out of 20 cases.
Once I got over the fact that I had learned the basics of Perl in all the wrong ways by an uncredible author, I turned to the monestary for information. I also bought Learning Perl, and when I had a good grasp on that, Perl Cookbook and Programming Perl. Don't jump the gun; don't try to learn Perl in a day because Rome wasn't built in one either. Make sure you thoroughly understand Learning Perl before you make the jump.
Once you've learned the basics, and you're comfortable writing programs for everyday tasks, you can start to learn more specific things, with books such as Mastering Regular Expressions, Object Oriented Programming with Perl, Data Munging with Perl, Programming the Perl DBI, and Mastering TK Perl. Perl is very enjoyable and useful as long as you take it at the right speed.
Look ma! I'm on CPAN!
munchie does perl: my very own perl site