When starting the cpan utility for the first time you're presented with a set of questions whose goal is to customise a configuration module; among the questions there are also requests to know which system programs should be used, like wget, ncftp and so on.

That could be a good example, in many senses: first of all, having an external configuration file where one can put weird paths for some needed external program; secondly, to get a clue about how actually check that there is some needed external software, and bail out if it's not available (which gives you dependency check as well).

Regarding hard dependencies and tests, you could make a test for the dependency. Something along the lines:

use Test::More tests => 1;
use English qw( -no_match_vars );

qx{ wget --version };
is($CHILD_ERROR, 0, 'wget is available');
[download]