I'm in the Washinton DC Area and for some reason the CGI Programming with PERL books hasn't come in yet ( due in the 15th ), but given O'Reillys reputation I would stake a lot in that book for CGI Programming.
I'm just reading my copy (so my opinion may change later
on) but it seems like a worthy replacement for the first edition and well worth the wait. I'm not sure, however, that it's really suitable for a beginner. It explains CGI and HTTP at a beginner level, but it assumes quite a knowledge of Perl.