The problem isn't Perl 5.8, it is Red Hat 9. CGI.pm was packaged separately by Redhat. I think this is done because it wasn't core in old versions of Perl, to allow the module to be upgraded separately.

The solution is to install the perl-CGI package. There are other core modules that are in separate packages. I forget what they are right now, but I had an earlier comment about them on perlmonks.

The problem is that it doesn't get installed by default and confuses lots of people that expect perl package to include all the core modules. This was changed in Fedora Core 1; CGI.pm is in perl package.