You can also check out perlretut, new as of perl 5.6.1; as well as Japhy's regex book.

Update: perlretut is new as of 5.6.1, not 5.8.0