The redirect method works by creating a header, so the second call to header is treated as the main body of the returned page.

To fix you simply need to include the cookie in the header created by the redirect method as demonstrated in the resource Your Mother linked to:

use CGI;

use strict;
use warnings;

my $q = CGI->new;
my $cookie = $q->cookie(
    -name=>'lizzy',
    -value=>'Lizzy',
    -expires=>'+12h',
);

print $q->redirect(
    -uri => 'http://perl.about.com/',
    -cookie => $cookie,
);
[download]