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.