If the dependency is necessary for your module to be usable at all, then check it is installed in Makefile.PL, and die if it's not found. That way, testers will bail out as soon as possible, before running any tests, and won't submit failure reports to the CPAN Testers service.

If the dependency is necessary for your test suite, but your module is still at least partly useful without it, then check it is installed in each test case that requires it, and skip the test if it's absent.

Your module in particular seems to belong to the first category.