The
Common Gateway Interface system was developed fairly early in the history of original
NCSA webserver. The goal was to allow for "interactive" web pages in concert with the newly created "
HTML forms" feature of
Mosaic, and to do so in a roughly generalizeable way. The
markup and communication
protocols created at the time to govern this process have remained almost entirely unchanged to this day.
Ordinary webservers had until then simply received filenames and transmitted files - rather simple. The NCSA team looked at several alternatives whereby a web page could be generated on the fly, via code, and settled on the quickest and dirtiest solution:
A request for a file arrives. If that file is determined to be a CGI, rather than being sent directly to the client, it is instead executed, provided with the data the client collected from the HTML form (in an encoded format), either via it's stdin or an environment variable. That "CGI Program" does whatever it likes with the data - it is in all respects a normal executable of the web server's host operating system - and then produces output on its stdout channel which is, more or less, sent directly back to the client's web browser.
The entire gamut of executable types has been exploited to operate as CGIs at one time or other: C and C++ programs, shell scripts, and PERL scripts are among the most common.
As idoru mentions, the first thing in that output is formalized to be the mime type of the following data, the accidental omission of which confuses many first time CGI authors. This is an intelligent design decision by the system's designers, as CGI's may generate not just a new web page, but images, audio, video, or any other kind of data which the web browser can handle, on the fly.
CGI's and forms represent a turning point of the World Wide Web as a medium. They quickly became ubiquitous, and the core of that mechanism has become something like the heart of the functioning web.
As site designers and developers quickly discovered, the mechanism of the CGI itself, which refers specifically to the interface between the standalone executable and the webserver, was ineffecient to use on a large scale, since processing each page request would require a fork and an exec call, churning OS resources to start and then eventually terminate an (often large) executable process over and over again for each hit, filling process tables and swap space, and in general making poor use of the way Unix allocates resources.
Many web application designers would address this problem by going on to create custom webservers which would directly perform the specific kind of automation they required; many of the web's most popular sites are the result of this custom ground-up programming.
As general purpose webserver designs matured, however, almost all of them drifted towards a "module" system as a kind of middle ground. Thus, the standalone CGI executable was replaced by a library, integrated either statically at compile time or on demand at runtime. These module interfaces typically included a more sophisticated interface to the webserver's various resources, especially shared memory and persistence. A majority of the automation now operating on the internet works via modules - a significant scalability win. Module-driven automation is not technically a CGI at all, since it does not at any time refer to the Common Gateway Interface; however, the term "CGI" has become synonymous with web-based applications, and is often misapplied to refer to them all.
It is also worth mentioning the evolution of the CGI-based script into the incarnation it enjoys today - for instance, on this site. Shell scripts in general and PERL scripts in particular suffered from the efficiency problems of CGI invocation; the repetitive invocation perl's often large runtime interpreter to handle each page request was was a scalability nightmare that was bringing many sites to their knees under load conditions. However, PERL, as well as a number of other scripting languages (some, like PHP, were designed more recently, explicitly for creating CGI's) were too cheap and convienient to give up easily.
The solution eventually settled on by the industry has been the script interpreter web server module, containing a single persistent interpreter which handles all the transactions. Only one copy (per server process) need be kept in memory, it is initialized only once, at server start, and it can theoretically afford variable continuity between transactions. Apache's mod_perl is an excellent example. The vast majority of web automation written today is written in a scripting language against this or a similar type of system (PHP, ColdFusion, etc).