This seems to work:

#!/usr/bin/perl
use strict;
use warnings;
use WWW::Mechanize;
my $browser = WWW::Mechanize->new;
my $distanceFinderURL =
  'http://www.randmcnally.com/rmc/directions/dirGetMileageInput.jsp';
my $distIn = $browser->get($distanceFinderURL);
die( "Can't get $distanceFinderURL -- ", $distIn->status_line )
  unless $distIn->is_success;
$browser->form('frmGetDirections');
$browser->set_fields(
                      'txtStartCity'  => 'Miami',
                      'txtStartState' => "FL",
                      'txtDestCity'   => 'Albany',
                      'txtDestState'  => 'NY'
);
$browser->submit();
$browser->content =~ /Driving Distance:.*?(\d+) miles/;
if ($1) {
  print "distance: $1 miles\n";
} else {
  print "couldn't find the 'Driving Distance' string on the page\n";
}
[download]

The problem might have to do with some hidden fields in the form. WWW::Mechanize takes care of all that stuff behind the scenes, that's the great thing about it.