Assuming you have mod_Perl available, which is alas mostly not the case, if you have written your scripts well, you can more or less make them run in "PerlRun" mode, which will run many CGI scripts more or less unmodified under mod_Perl, and deliver a measureable performance boost by avoiding all that forking.

Ideally you want to create Apache::Registry scripts, where you can write normal Perl, and have Apache/mod_Perl compile and cache it for you. You have to make sure you have written good code, as any problems will bring down the whole web server - and the fear of this is an oft quoted reason why most hosting companies won't offer mod_Perl.

To get the most out of mod_Perl you'd skip the CGI emulation of the above aproaches, and write pure Perl directly into Apache, which is very cool, and not for the feint of heart.

I don't claim to be a mod_Perl expert, so I'm sure some other more learned monks can offer additional advice. I'd have a look here for a start though:

• mod_Perl Home page
• Writing Apache Modules with Perl and C
• mod_Perl Cookbook
• Stas Bekman's column on perl.com
• mod_perl: Is it so necessary?
• Good mod_perl tutorial
• mod_perl vs CGI: benchmarks and code
• Good place to learn Apache::PerlRun - my very first question here...!
• How common is mod_perl?
• mod_perl, The Bane of Shared Webhosting

Update: Extra links added.

I'm guessing that if it was, though, your host would have suggested it. You may have to go the php route.
--
Mike