I'm a bit late to the TIMTOWTDI party, but here's my contribution: Module::Load::Conditional's check_install with Data::Dumper (both are core modules):

use Module::Load::Conditional qw/check_install/;
use Data::Dumper;
print Dumper( check_install( module => 'Some::Module' ) );
[download]

So how do these things work? Does every server have every Perl package ever written residing on it?

No, but: Perl comes with a set of "core" modules, as the other Monks have mentioned. Some OS distributions actually strip out some of these core modules, but in my experience on web servers, that's rare - so you can almost always rely on these core modules being available. In addition, many distributions of *NIX OSes will include a bunch more Perl modules, those required by the other packages installed on the machine. (Or, in the case of Windows, pre-packaged Perl distributions like Strawberry Perl will include a bunch of modules often needed by users - example.)

In the case of *NIX OSes, this initial set of modules will usually be installed via the system's package manager, like apt or yum. System administrators then have the option of installing additional modules either via the package manager or via tools like cpan or cpanm (although using those to install modules into the system Perl is not something I'd recommend, but that's a topic for another post). System admins also have the option of installing whole different versions of Perl, in case their users need them. For example, Pair, which hosts this site, provides at least 5.10.1, 5.12.2, 5.14.1, 5.16.2, and 5.22.1 and a ton of pre-installed modules, most likely based on popular demand by users (Update: I should also mention that typically each Perl installation will get its own independent set of directories into which it installs its modules). Installing modules into those custom-built Perls is then usually done via the aforementioned cpan/cpanm tools.

Or if the unusual::unique module is not on the server, how would anyone request it to be so?

In the case of web servers, you can probably try submitting a support ticket, and often ISPs will consider installing additional modules system-wide if they are requested by enough users. Otherwise, if they won't do it for you, it depends a bit on what kind of access you have to the web server. If you have shell (ssh) access, there are ways to install modules into your home directory either by hand or using a tool like local::lib, so that they are available only to your user and your website. If you don't have shell access (FTP-only or whatever), things are a little more tricky - but for Perl modules that are pure-Perl, i.e. they have no C/XS components that need to be compiled on the server, often it is still possible to get them onto the server, but that's also a topic for another post.