Take a look at how do I set a cookie and redirect in the PerlMonks Categorized Q & A section. This shows one way to do it.

I'm a little rusty in this area, but I believe the problem with the way you were trying to do it is that "$session->header()" call is setting the coookie and sending the headers in one call, but redirect needs to come before the headers, so after the header() call is too late. Doing your own headers, as in the Q & A, allows you to get the components in the right order.

The second answer in the Q&A avoids the problem by using refresh instead of redirect.

Update: Fixed Link. (Thanks shmem)