Well the CGI.pm and cgi-lib.pl are similar in many respects, but they are new types of programs that are helpful for designing perl cgi programs.
What they do is this, they take the same basic routines found in most code and simplify them. Like, taking information from a form for example. Instead of writing complex code to change it from CGI to something useful that perl can deal with, you can use these programs along with your program and called a simple reference like & ReadParse; to do all the work.
Want to print the headers needed to return a web page "on the fly"? Instead of worrying if you got the mime headers correct, you could use &PrintHeader;. These programs do alot more than that though and the particulars is where they start to become different.
cgi-lib.pl was just upgraded. It now has some of the features previously only available in CGI.pm . Some of those new things are file uploading through netscape and the multipart/form-data encoding method. It is also perl 4 and perl 5 operational.
CGI.pm is a perl 5 module on the other hand. It has been using the multipart/form-data encoding method for a while now and has a complete set of functions to call for making forms instead of using html. It has many different options and is worth the lookover.
Note of reference CGI.pm is already installed on the server.What makes these tools nice is that they combine many different tasks common in the perl/cgi enviroment into one script. WWWlib-perl was made with the same ideas in mind. It goes on to use other scripts in it's library, to check for errors, give ways to do local file requests, html manipulation and other such things...
I would advise using all three and taking the strengths from each one. Using these routines cuts that simple mail script you want to write from alot of code, to something that is alot easier to handle.