First, what you have there should work for Apache.

>perl -e "use CGI qw( redirect ); print(redirect(-uri => 'http://www.e
+xample.com/page.html', -status => 301))"
Status: 301
Location: http://www.example.com/page.html
[download]

What server are you using? For some servers (e.g. IIS), you need to send an HTTP status line instead of the pseudo-HTTP "Status" header.

>perl -e "use CGI qw( redirect ); print(redirect(-uri => 'http://www.e
+xample.com/page.html', -status => 301, -nph => 1))"
HTTP/1.0 301
Server: cmdline
Status: 301
Date: Mon, 26 Mar 2007 15:59:21 GMT
Location: http://www.example.com/page.html
[download]

Secondly, are you sure that's the script you executed? If it doesn't work, it should fail by displaying a 500 error, by displaying some other error or by displaying a blank page. It should not fail showing the HTTP header. In order to display what you said it displayed, it would have had to print a CGI header before the first print.