Generally, I use moritz' second-last listed approach, "Search relatively to the installation path of the binary" (well, of the script).

use File::Spec;
my $project_dir = File::Spec->catdir( File::Spec->rel2abs(__FILE__), F
+ile::Spec->updir() );
[download]

I put that in my main script, right near the top, maybe in a BEGIN block if I have to:

use File::Spec;
my $project_dir;
BEGIN { $project_dir = File::Spec->catdir( File::Spec->rel2abs(__FILE_
+_), File::Spec->updir() ); }
[download]

and then everything is relative to that. I used to use this to create my @INC path, but have recently been shown rlib which takes care of that for me now :-)