Learning Perl (a.k.a. the Llama book), by our own Randal L. Schwartz and Tom Christiansen, has an entire chapter on CGI.pm which I find extremely helpful. It nicely supplements the example-laden documentation which comes with CGI.pm.

The Llama book and Lincoln Stein's own copious documentation really ought to be all one would need to get started.