The Common Gateway Interface is very correctly named. It defines an interface which allows programs to act as a gateway between the web server and the web browser, allowing any common program [written in any programming language] to take user input [by the way of HTML forms] and output HTML which is sent back to the user's web browser. This allows for a somewhat limited form of interaction, the limits of which can be overcome by a little more work by the programmer.
CGI programs can be written in any programming or scripting language which the web server [the machine which is running the CGI programs] can run. This means that CGI programs can be written in C, C++, Java, perl, Unix shell scripts, TCL, or nearly any other programming language; all that is required is that the programming language have facilities for accessing standard input, standard output and environment variables. Perl, however, is a common choice because of it's interpreted nature and excellent text-processing abilities.