This should help though I don't have time to cook up a full working example today-
print CGI::redirect( -uri => $whatever,
-cookie => $session->cookie,
-status => 302 );
You can send cookies with redirects. I don't know if CGI::Session has the ability to do headers like that but CGI.pm definitely does so give the above a shot. Remember to be careful not to double print headers. Test from the command line to be sure about the output if your code isn't trivial. The browser and server can disguise problems.