Yes, the shared code should probably be in a module (.pm) file, but in what directory should I put that file and possibly what options should I give to ExtUtils::MakeMaker. The tests should find this module file no matter how I invoke the tests, but the file should not be installed by make install.

I typically put such files in the t directory, and start the test files with something like:

BEGIN {
    chdir '..' unless -d 't';
}
use t::Whatever;
[download]

or

BEGIN {
    chdir 't' if -d 't';
}
use Whatever;
[download]

or

BEGIN {
    chdir '..' unless -d 't';
}
push @INC, 't';
use Whatever;
[download]

Now that only allows you to run the tests either from the 't' directory, or the top-level distro directory (using either "make test", "prove", or a path to the test file), but I've never felt the urge to run the tests from any other directory.

t/lib is traditional. Put use lib 't/lib' at the top of the .t files so that they can find the shared code. You don't need to tell EU::MM anything special.