Beyond the normal measures described to make general Perl programs faster or smaller, a CGI program has additional issues. It may be run several times per second. Given that each time it runs it will need to be re-compiled and will often allocate a megabyte or more of system memory, this can be a killer. Compiling into C isn't going to help you because the process start-up overhead is where the bottleneck is.
There are two popular ways to avoid this overhead. One solution involves running the Apache HTTP server (available from http://www.apache.org/ ) with either of the mod_perl or mod_fastcgi plugin modules.
With mod_perl and the Apache::Registry module (distributed with mod_perl), httpd will run with an embedded Perl interpreter which pre-compiles your script and then executes it within the same address space without forking. The Apache extension also gives Perl access to the internal server API, so modules written in Perl can do just about anything a module written in C can. For more on mod_perl, see http://perl.apache.org/
With the FCGI module (from CPAN) and the mod_fastcgi module (available from http://www.fastcgi.com/ ) each of your Perl programs becomes a permanent CGI daemon process.
Both of these solutions can have far-reaching effects on your system and on the way you write your CGI programs, so investigate them with care.
See http://www.cpan.org/modules/by-category/15_World_Wide_Web_HTML_HTTP_CGI/ .
A non-free, commercial product, ``The Velocity Engine for Perl'', (http://www.binevolve.com/ or http://www.binevolve.com/velocigen/ ) might also be worth looking at. It will allow you to increase the performance of your Perl programs, running programs up to 25 times faster than normal CGI Perl when running in persistent Perl mode or 4 to 5 times faster without any modification to your existing CGI programs. Fully functional evaluation copies are available from the web site.