C'est effectivement dans le répertoire /cgi-bin/ qu'il faut mettre ton script perl, et tu l'appelles à partir d'une page html comme celà :<a href="/cgi-bin/truc.pl">truc</a> par exemple.
 
A priori ça devrait marcher sauf si ton conf/default/httpd.conf est mal réglé sur le serveur de ton hébergeur (voir les docs du serveur apache).
peut etre qu'il ne reconnait pas les .pl (à rajouter dans httpd.conf ...)
 
bref à toi d'enqueter à ce niveau là ... bon courage