response to myself ... you don't need HTTP::Headers at all. Here's working code, culled from perldoc lwpcook and modified to fit your example (note, the only module you explicitly have to use is LWP::UserAgent) :

#!/usr/bin/perl -w

use strict;

use LWP::UserAgent;
my $ua = LWP::UserAgent->new();

my $req = HTTP::Request->new(POST=>'http://212.87.65.227/bin/query.exe
+/en');
  
$req->content_type('application/x-www-form-urlencoded');
$req->content('to=Guildford&from=Portsmouth');
my $res = $ua->request($req);

if ($res->is_success) {
 print $res->content;
} else {
 print "Error: ", $res->status_line, "\n";
}
[download]