Although it might not be perfect, here is what I do for XML::Twig. Note that none of the modules I check are needed, so just display messages if I don't find them, but I would think that dying should stop the installation process.

The Makefile.PL file includes a line that runs this code:

#!/bin/perl -w

# $Id: check_optional_modules,v 1.2 2003/09/24 13:35:07 mrodrigu Exp $

use strict;

exit if( $] >= 5.008); # Encode is there, so is Scalar::Util

if( $] >=  5.0060)
{ unless( eval 'require Scalar::Util' or eval 'require WeakRef' )
      { warn "Neither Scalar::Util  nor WeakRef is  installed. ",
             "Installing  one of these modules  would  improve ",
             "XML::Twig memory management and eliminate memory ",
             "leaks when re-using twigs.\n";
      }
    else
      { warn "weaken is available\n"; }
  }

unless( eval 'require Text::Iconv')
  { my $version= `iconv -V` || '';
    if($version)
      { warn "The iconv library was found on your system ",
             "but the Text::Iconv module is not installed. ",
             "Installing Text::Iconv would make character ",
             "encoding translations fast and efficient.\n";
      }
    else
      { warn "Did not find iconv\n"; }
  }
else
  { warn "Text::Iconv is installed\n"; }
[download]

I also run a script that creates the real .pm file from the file I maintain. Amongst other things, this script turns qr// constructs into plain strings for (very!) old versions of Perl. You could probably use such a trick to turn no warnings 'once'; into local $^W = 0;.