Is there somewhere specific where I should install it?

It does not really matter much, I usually install it as my normal user (not as root) to my home-directory (a subdir of my home that is).

Presumbly I then have to change the line at the top of my perl scripts from #!/usr/bin/perl to this new path?

Yes, that's right and you should also set the PATH-enviroment variable (or whatever your shell uses as search-path) up in such a way that your "new" perl is found before the "old", so that you can simply type "perl" on your command prompt and get the new one.

how will CPAN know to put these in my new perl installation path and not the system perl?

On installation perl remembers where it is installed and so knows where to install modules (just don't mess with the defaults during installation).

You later then only have to run the proper perl and everything will be sorted (i.e. wether you run it via perl -MCPAN -e shell or simply via cpan you just have to make sure that your shell is picking up the newly installed perl/cpan).