For all of the admins who threw their computer out the window and swore they would never use CPAN again when they tried to install Net::SSH::Perl, try the following two things:
1. Install the GMP library(not the perl one) apt-get install libgmp-dev
2. Use cpanm instead of cpan. i.e. cpanm Net::SSH::Perl
This should solve the following error:
GMP.xs:4:17: error: gmp.h: No such file or directory
Also, while I am talking about it, check out perlbrew. It allows you to easily set up self contained instances of perl for multiple versions and switch between them. The possible uses for this are nearly endless, but I find that it increases my “sense of adventure” when messing with perl modules and my environment since I am not affecting the system perl.