Here's some random ideas, although this is hard to discuss without seeing the server itself. This is about the minimal code you need for the CGI to work.
print "Content-Type: text/html\n"; #Tell browser it's html
print "\n"; #IMPORTANT-End of header.
print "Hello World"; #Output
It works on my server (IIS4/Activestate), so if it doesn't work on yours, then you know the problem is in configuration. Otherwise you should post your code.
Oh, and this is named HelloWorld.cgi on my server. See if the .cgi extention works (it may need to be in the cgi-bin directory, I forget)
-Lexicon