What is the "CGI Overhead", and should I be worried about it?

The CGI Overhead is a consequence of HTTP being a stateless protocol.
This means that a CGI process must be initialised for every "hit"
from a browser.
In the first instance, this usually means the server forking a
new process.  This in itself is a modest overhead, but it can
become important on a heavily-used server if the number of
processes grows to problem levels.
In the second place, the CGI program must initialise.  In the
case of a compiled language such as C or C++ this is negligible,
but there is a small penalty to pay for scripting languages such as Perl.
Thirdly, CGI is often used as 'glue' to a backend program, such as
a database, which may take some considerable time to initialise.
This represents a major overhead, which must be avoided in any
serious application.  The most usual solution is for the backend
program to run as a separate server doing most of the work, while
the actual CGI simply carries messages.
Fourthly, some CGI scripts are just plain inefficient, and may
take hundreds of times the resources they need.  Programs using
system() or `backtick` notation often fall into this category.
Note that there are ways to reduce or eliminate all these overheads,
but these tend to be system- or server-specific.  The best-supported
server is probably Apache, as commercial server-vendors may prefer to
push their proprietary solutions in preference to CGI.