Apache2の設定を以下のように変更する必要がある

1.CGIプログラムを設置するディレクトリの指定
 以下ファイルの内容を編集
 /etc/apache2/sites-available/default
 CGIプログラムを動作させたいディレクト
 以下の行を追記もしくは編集する
 Options FollowSymLinks MultiViews ExecCGI


2.CGIスクリプトとして動作させる拡張子を認識させる
 以下ファイルの内容を編集
 /etc/apache2/mods-available/mime.conf
 以下の行を追記もしくは編集する*1
 AddHandler cgi-script .cgi .pl


3.Apache2の再起動
 /etc/init.d/apache2 restart

*1:コメントアウトされているだけの可能性があるので、コメントを解除する