When people ask this sort of question on c.l.p.m I usually point them to Introduction to Perl & CGI Programming although I have to say that I've never read the whole thing myself.
It's based on David Medinets' book, Perl 5 By Example, and from the little I've read it seems to be aimed at beginners.
Use strict and -w don't seem to arrive until Chapter 15,16ish but are used in the examples.
It's the only online tutorial I've found so far for CGI and Perl, if anyone knows of a better one I'd like to know.

Ugly
... And then they asked me for a signature!