whilst this is confusing for those new to perl/CGI...all the problems stem from the fact that the environment for a perl CGI in Apache is different to the environment you execute perl scripts directly yourself.
for a start, paths and file/directory permissions need to allow Apache (which runs as nobody or www user) to access perl + modules. Then you may also need to either configure Apache to run the cgi with perl by knowing the extension of the script (e.g. .cgi) OR you need to use a "shebang" line at the start of the script telling Apache (or anything else) that it needs to be executed with perl.
if you are the admin of the computer, you can "su - nobody" or "su - www" and try to execute your CGI script, to check for correct perl and file permissions. Also "telnet localhost 80" and then "GET /cgi-bin/yourcgi" sometimes gives more clues than "premature end of script headers".
Have fun with CGI, and be careful if you Apache is accessible on the internet, as CGI scripts can open up a vector for the box to get hacked.