Try this on the CLI:
perl -e 'print join("\n", @INC);'

And you will see that for example in my system it is here with /usr/share/perl/5.8.0 being in my @INC:

barrd:~# locate Basename.pm
/usr/share/perl/5.8.0/File/Basename.pm
[download]

Update: Added more text to make a bit more sense

The module isn't Basename, it is File::Basename. It lives in a file named File/Basename.pm. But the package is "File::Basename". It is used like this:

use File::Basename;
my $file = basename($path);
[download]