Doing this requires a fair amount of work, which HTTP::Request::Common makes much easier. Here is a short example that works for me:

#! /usr/local/bin/perl
use strict;
use LWP::UserAgent;
use HTTP::Request::Common;

my $ua = LWP::UserAgent->new();
my $response = $ua->request(
  POST 'http://localhost/cgi-bin/file.pl',
  Content_Type => 'form-data',
  Content => [
    arbitrary       => "with",
    parameters      => "corresponding",
    here            => "values",
    "uploaded file" => ["example.txt"],
  ],
);
if ($response->is_success()) {
  print $response->content();
}
else {
  print $response->error_as_HTML();
}
[download]

where file.pl is a quick file upload CGI script I wrote (it just echos back the file) and "uploaded file" is the name of the cgi parameter for the uploaded file. I included some random CGI parameters just to show how to do it. For more options you can see the documentation.