Put HTML::Template into a subdirectory ('lib') of the directory your application (or CGI) is in, then add
use lib qw(lib);
at the top of your script. It side-effects @INC.
This is a good solution because it will work even if you only have FTP access to a site (not login). Also, HTML::Template is only one file to install (Template.pm within the HTML folder).