Assuming you already have an Apache server (or compatible server that reads a shebang! line - more on this in a moment) and a perl installation running, it is fairly simple to start running a perl program on the internet.
First, you must have some way to access the program. Here we will deal with form data and submission, so we will assume that your form code in HTML has a property saying ACTION="programname.cgi".
The Initial Setup 
CGI scripts begin like any other Perl program, with a "shebang", something like:
(see Perl Programming/First Programs for details)
Next load the CGI module:
The CGI module makes our work easy because it has pre-programmed functions in it for internet use. Then we must create a handle to CGI - something that allows us to access the functions. We do this with:
my $query = CGI->new();
This means that the variable $query is loading the CGI standard functions.
Now that our program is setup using the CGI module, it should look something like this:
#!/usr/bin/perl use CGI; my $query = CGI->new();
So we have a program, it just doesn't do anything yet, and will actually cause a server error because the server has no output or any idea of what kind of output to display even if it had some.
Retrieving Information 
Before we tell the server what to do with our output, we need to retrieve our input. To do this, we use the $query variable we declared earlier. Say we have a text box in the form that is named "Name" and we want to find out what was typed there. To do this, we put the following line of code in our program:
my $Name = $query->param('Name');
Now, this line of code introduces us to the param() function (for "parameter"). The param() function can do quite a few handy tricks for us, all of them nice ways to retrieve our variables. It processes all of the http coding so all we get is a nice clean variable. Another note, you aren't required to use $Name as your variable. It's simply more convenient to only remember one name for the same variable. Still, use what's best for you.
Now we must create our header information. CGI even makes THIS easy for us. Instead of memorizing a bunch of mime-type declarations (which you may do as well), all we must do is type:
and it prints out our header information. A note about headers. Inside the parenthesis, we may specify parameters like cookies to send to the user's browser. This becomes very useful later. For now we will just stick to the headers.
The last thing you need to put (though the program will run, displaying a blank page without it) is some output. Let's simply have it display the user's name back to him/her. This would look like.
print " You said your name was: $Name";
The Finished Code 
So we now have a complete program that processes a form, using only 6 lines of code. Isn't Perl great? The final code looks like this:
#!/usr/bin/perl use CGI; my $query = new CGI; my $Name = $query->param('Name'); print $query->header(); print "You said your name was: ", $query->escapeHTML($Name);
When put into perspective, we can see that the $query variable is a very important connection to the CGI module as it tells perl that the function you are referencing belongs to CGI; Again, you may declare any variable name in the place of $query so long as you are consistent, though you will find many developers use $query or $q. Also note the use of the escapeHTML method to avoid any HTML injection problems.
Final note. Make sure you change /usr/bin/perl to the path of your perl installation (assuming that is not it) so perl will execute properly
There are a number of CGI frameworks to help with common CGI programming tasks: