O'Reilly have a knack of producing no-nonsense, Straight to-the-point indespensable technical books from a whole range of programming technologies and languages. Of course the Perl series is unrivaled for it's attention to detail, conciseness and cold hard facts. 'Learning Perl' now in it's 4th edition is aimed at the newcomer to Perl (not neccessarily complete proramming newcomer), and teaches the basics extremely well. It cuts out the more difficult topics, and focuses on the syntax needed to branch out into whatever ever use of Perl you wish.
A great introduction to Regular Expressions is included, Although, this seem at first a more advanced topic (to a complete newbie) they are dealt with in a succint, descriptive manner which makes Regex seem easier to deploy than first thought.
If you are put of by 1000+ page books that assume your an idiot (or dummie), then 'Learning Perl' is a great place to start your adventure. It is also ideal preparation to take on the mighty 'Camel' book.