I've never used HTTP::Headers, instead I use HTTP::Response or CGI. Doing it with CGI is easy:

use CGI;
my $q = new CGI;
print $q->redirect(-uri=>'http://blah.com/blah');
[download]

Which returns:

Status: 302 Moved
location: http://blah.com/blah
[download]