Du brauchst das dev-Paket der libgd, wenn du das Perl-Modul installieren willst: libgd2-dev
Btw, es gibt das GD-Paket auch fertig: libgd2 oder libgd2-noxpm oder libgd2-xpm mit jeweils entsprechenden dev-Paketen dazu.