Each subroutine should be tested individually. Consider this contrived and silly example:

use List::Util qw(sum);
use Scalar::Util qw(looks_like_number);

use Test::More;

ok looks_like_number(1), 'Found a number.';
ok !looks_like_number('a'), 'Rejected a non-number.';
is_deeply [map {$_ + 1} (1,2,3,4)], [2,3,4,5], 'Correct mapping.';
is_deeply [grep {looks_like_number($_)} qw(a 1 b 2 c 3 d 4)], [1,2,3,4
+], 'Correct filter.';
cmp_ok sum(1,2,3,4), '==', 10, 'Sum was correct.';
cmp_ok sum_of_incremented_nums(qw(1 a 2 b c 3 d 4)), '==', 10, 'summed
+ dirty list properly.';

# Integration:

sub sum_of_incremented_nums {
    return sum(map{$_+1} grep {looks_like_number($_)} @_);
}
[download]

Here we've tested (minimally) all the components individually, and then tested the thing that uses the components.

How to deploy? A really simple way is to use the features of ExtUtils::MakeMaker. It can place your modules where modules live, and your executables where they're supposed to live on a given system. And the user is able to specify alternate locations based on environment settings and on how Perl was compiled and where it lives. You'll have a Makefile.PL that generates a makefile customized for your specific needs. The makefile will create the proper make directives, and you'll have 90% of what goes into a CPAN distribution when you're done. Consider any module on CPAN that bundles an executable script as part of the distribution as prior art. I haven't looked recently, but Carton, App::cpanoutdated, App::cpanminus, Devel::NYTProf, Perl::Critic, and Perl::Tidy are all examples of CPAN modules that bundle executables.

That said, you might also consider a minimal packaging system like Carton. Or combine that with something like Docker where you have more control over the isolated environment.

As for a structure, I typically do something like this:

./projectdir
            \
            \
             - projectdir/lib/
             - projectdir/bin/
             - projectdir/t/
             - projectdir/xt/
             - projectdir/README
[download]

In your executable (projectdir/bin/foo) you might do something like this:

#!/usr/bin/env perl

use strict;
use warnings;

use FindBin qw($Bin);

use lib "$Bin/../lib";

use MyModule;
...
[download]

This works in situations where you aren't deploying the module to a location known to PERL5LIB and not known to some tool such as Carton.