Verifique se você definiu o caminho a seguir em /etc/apache2/apache2.conf :% ScriptAlias /cgi-bin/ "/path/to/cgi-bin/" e se seus scripts estão nessa pasta.
Se seus scripts terminarem em .pl, certifique-se de alterar a linha de AddHandler cgi-script .cgi to AddHandler cgi-script .cgi .pl
em /etc/apache2/apache2.conf e verifique se ele não está comentado.
Options FollowSymLinks +ExecCGI precisa ser configurado no seu host virtual.