A module is a very freaking diff thing.
Hear, hear!
1. Make a script that "uses" your module. It doesn't matter that your modules isn't written yet, this is practice toward how you would like to use or expect your module to be used.
2. Turn your pretend script into usable tests; make sure to include tests that will intentionally fail.
3. After #1 and #2, then start coding on your module to actually deliver what your tests expect.
As others have mentioned, go check out
Perl Best Practices. For those less patient, the Top 10 can be found on perl.com here:
http://www.perl.com/pub/a/2005/07/14/bestpractices.html
cheers.
ryanc