My testing practice is that I refuse to modify code unless at least one test has been defined on it. That lets me apply tests where they're needed, but means I don't need to interrupt development until I can develop a battery of tests for all known functionality. I use (as I suspect you do) the standard Test and Test::Harness modules, and am more-or-less satisfied with them.
Initially, I took a look at the PerlUnit module on xprogramming. In my humble opinion, it's not too well documented and lacks a standard install. Plus, PerlUnit seems to be by default packaged in a ZIP file-- slightly more Windows-specific than I'd prefer.
The CPAN TestUnit module seems more versatile and mature, and I'm a bit surprised that the xprogramming page doesn't link to it instead. (No offense to the author of PerlUnit, whoever she may be.) TestUnit generates both xUnit-friendly and Test::Harness-friendly output. (This is based primarily on reading the docs, not from actual use.) It's based on JUnit, which I've used and I like. Like JUnit, it has good support for setup and teardown of tests. I intend to try using it on future projects.
In terms of actual testing functionality, I haven't seen too much out there that the standard Test module doesn't offer. Test::Simple gives a way of naming tests. Test::Cmd is best for testing the output of external scripts and programs.
For CGI scripts, CGI::Test allows you to run your scripts from the command line as though they were running in CGI context. I haven't tried using it yet, but I will as part of this discussion, and will post the results here.
In actual practice, I use the regular Test module (like I said) and supplement it with some modules of my own, which I'm working on packaging up for CPAN (hopefully sometime this week). The primary things that Test is missing, in my experience, are output tests. Things like:
Anyway, I'm working up some examples, both of applying refactorings and of tests, and will be posting further followups. There's a great deal to explore here, and PerlMonks is the place to do it!
Update: Corrected a misstatement about Test::Cmd.