In my experiance, at least for Apache server and IIS for windows a #!perl is necessary. this same line is not necessary for console programs, which sometime confuses new users because the console spits out valid HTML, but they get 500 errors from a browser.

Generally if perl is on the path(usually the case with active state install) #!perl will do it, otherwise you need the full #!C:\Perl\bin\perl you can add .exe to that but it's not necessary.

You can configure apache to recognize .cgi as a file to be interpreted by perl, but this is not general practice because cgi programs can be written in many languages.

One (possibly obvious) thing to note cgi scripts usually can only be run from specific directories, commonly cgi-bin, but I've seen it be called "scripts" as well.