Books

Perl and CGI for the World Wide Web
This books excels at providing excellent visual examples, but can be confusing if you've never done programming before.
Learning Perl
Here's the book you'll need to get started with down and dirty Perl programming. Very well written and recommended by the experts.
Programming Perl
A highly recommended resource after reading "Learning Perl".

Web Resources

CGI-Java.com
A good starting point for CGI, Java or JavaScript.
Perl.com
This site is good for folks who are familiar with Perl and CGI concepts.
CGI Made Easy
Need a quick primer to CGI? Here's the place to go!