After running into this problem several times, I've standardized how I place script and module files in each project. Basically in my project directory, I have a sub-directory for scripts (e.g., cgi-bin) and a sub-directory for my modules (my_lib). Then I can include the following code in any script and it always finds my modules.

#---------------------------------------------------------------------
+--
# Portably Include My Perl Modules
#---------------------------------------------------------------------
+--
use Cwd;
use File::Spec;
my $dir;
BEGIN
{
    # Prepare lib path
    $dir = Cwd->getcwd; # Get directory path of script or get web doc 
+root
    my @dirs = File::Spec->splitdir( $dir ); # Split path into array
    pop @dirs; # Take off last directory (e.g., public_html, cgi-bin,.
+..)
    # Put'em togeth & add modules dir
    $dir = File::Spec->catdir( @dirs, "my_lib");
    unshift(@INC, $dir) if (-d $dir); # Incl. my lib if it exists
}
[download]

Hope that helps,