Just to offer a contrary opinion :-)

My personal rule of thumb is to include as prerequisites all test modules that are needed to test module functionality, and leave as optional test modules that are used to test non-essential things like documentation, etc.

This is for a few reasons:

• My general experience is that it's better to have something fail early and fast in an automated test suite than it is to diagnose something after installation. So I think it's important for users to run the full test suite before installation.
• Allowing users to easily install with a failing test suite means that it becomes that much harder to figure problems with modules that depend on your module.
• The more times test modules appear in prerequisites, the more times they're going to get installed, the more likely they're going to be on a box the next time a module needs to use it for its test suite.

Note: I'm not saying that people should be forced to run the test suite. It's always possible to download and install manually, and ignoring test-specific prerequisites is fairly simple in almost all cases.

However I think that the fact that CPAN tests by default before it installs is one of the reasons that Perl's module system works so well - so I prefer to have maximal tests by default.

Another option that you didn't mention is to distribute a copy of the modules you need with your distribution (say in t/lib). This can work well, but I tend to avoid it myself because it increases the distribution size and you have to track bug-fixes / patches in third party modules.