There are a number of good Perl/CGI tutorials on the web.

Update: For starters, look at Ovid's Web Programming Using Perl. Not only does he explain what to do and how to do it, but he also explains what not to do (and how not to do it)!

(I should also have mentioned that there are even MORE bad tutorials out there.) :-)

This will probably get you going pretty quickly.

Impossible Robot