Unter Linux hast du immer Perl. Da brauchst du zu Anfang nichts zu installieren, zudem findest du viele Perl-Module im Paketmanagement und die lassen sich sehr leicht darüber installieren. Zudem gibt es Programme mit denen sich Module in Distributionspakete umwandeln lassen. z.B. dh-make-perl für Debian.

Wenn du unter Windows lernen willst dann installiere dir erst mal eine Distribution wie Strawberryperl oder Activeperl.
Du brauchst an sich kein spezielles Paket um CGI-Scripte zu schreiben. Fast jeder Webserver lässt sich so einrichten, dass du Perl für CGI-Scripte nutzen kannst.

Zu Anfang würde ich mich mich Konsolenscripten beschäftigen, hat man nicht noch die zusätzlichen Probleme mit HTML und CGI. Danach kann man sich mit CGI-Scripten auseinander setzen. Wenn man erfahrener ist wandert man ganz automatisch zu GUIs wie Tk, Tkx, Wx, Gtk2 oder Win32::GUI.

Ich habe einen ersten Schritte auf der Linux-Konsole gemacht und danach einen kleinen Webserver wie Lighttpd installiert. Nach einiger Zeit mit CGI-Scripten habe ich mich mit Gtk2 auseinander gesetzt.