AFAIK redirect is supposed to 'do the right thing'...
To check why it is not working, first run the script at the command line.
If that doesn't work tell us the code you are calling redirect with.
If that does work try talking direct to the server ie:

% telnet server 80
GET /cgi-bin/redirect_me.pl HTTP/1.1
[download]

If that doesn't work, CGI.pm can't figure out the right headers, or your server restricts headers that can be sent to clients.
If it did work that way then your browser doesn't understand the headers it is getting.

We can give more help if we know where things are going wrong.

Note: headers sent should be something like this:

Status: 302 Moved
Location: http://www.msn.com
[download]