When I convert the POST to a GET, I get an error:

Error 400: 

HTTP Web Server: Unknown Command Exception

So my guess is that they really want you to POST your data.

For such tasks, WWW::Mechanize is usually my preferred choice, for it makes stuff so easy. A sample script like this would get you started:

use strict;
use WWW::Mechanize;

my $mech = new WWW::Mechanize;
$mech->get('http://www.stat-usa.gov/nct_all.nsf/Search');
$mech->submit_form(
   form_name    => '_Search',
   fields       => {
        Query   => 'your search term',
   }
);
print $mech->content;
[download]