You don't need to make your distribution look like the structure that h2xs gives you, so stop worrying about h2xs. You can look at other utilities, like Module::Starter. You might want to create a fake distro just to see what it does and how it works. In the same way, you don't need a Makefile.PL to test, although it does help. You want to get there eventually, but if testing is more important at the moment, you can skip it for now.

You can use the prove(1) function that comes with Test::Harness. You tell prove where to find the modules, and which test files to run, and it handles the rest. If you write the tests first, this is the quickest way to get going.

I suggest that you start off so that you can move towards a Makefile.PL (or a Build.PL if you want to use Module::Build instead]. Put all of your tests in a directory named t since that's where Makefile.PL and Build.PL look for them by default.

As for writing the tests, I like to make a lot of small test files, usually one per function in the public interface at least. That's mostly a matter of taste. With prove, you can limit your tests to just the files you want, so if you have a lot of test files with a small number of tests, you can break down your testing easily. With only a couple of test files that each have a large number of tests, you might have to sit through a lot of tests that you don't care about at the moment.

Once you are ready to create the Makefile.PL, I suggest you look at a couple on CPAN and find one that looks simple and close to what you want, then copy it. You'll be able to tell Makefile.PL where to find the modules (they don't have to be in a lib/ directory), where to put other files like executables, and so on. The ExtUtils::MakeMaker documentation has all of the details, and don't let it scare you off in the first two minutes. ExtUtils::MakeMaker::Tutorial will help too, as will perlmodstyle and perlnewmod.

As for creating good test cases, look around and you'll find a lot of advice on testing. Good luck :)