If you are brand new to programming at all, I recommend
Beginning Perl, which you can get
freely and legally online (in an earlier edition, but I prefer that edition to the second printing anyhow).
If you have programming experience, then I recommend
Learning Perl preferably in the most current (5th) edition, since it has updates on a number of new features in Perl that earlier books don't discuss.
The Perl Cookbook is also excellent, as is Perl's internal documentation (which as Ghostdog says you can also find online), but I don't think I could have learned the language that way. I prefer a structured tutorial.