Personally, I prefer to use Test::Mores skip feature to skip tests whenever a optional (in general) but prerequisite (for the test) module is unavailable:

use strict;
use Test::More tests => 5;
my $have_test_deep;
BEGIN {
  eval {
    require Test::Deep;
    Test::Deep->import(Some => 'Parameters');
    $have_test_deep = 1;
  };
};

SKIP: {
  skip "Need Test::Deep for the tests", 5
    unless $have_test_deep;

  ok("I'm OK");
  ok("You're OK");
  ok("We're OK");
  ok("They're OK");
  ok("All's OK");
};
[download]

The Test::More documentation lists a different idiom of placing the prerequisite test in the SKIP block instead of the top of the test script:

SKIP: {
    eval { require HTML::Lint };

    skip "HTML::Lint not installed", 2 if $@;

    my $lint = new HTML::Lint;
    isa_ok( $lint, "HTML::Lint" );

    $lint->parse( $html );
    is( $lint->errors, 0, "No errors found in HTML" );
}
[download]

Updated: Fixed code in my example, added example from Test::More documentation