You should use err_headers_out( ), not headers_out( ), when you want to send cookies in a REDIRECT response or in any other non-2XX response. The difference between headers_out( ) and err_headers_out( ) is that the latter prints even on error and persists across internal redirects (so the headers printed for ErrorDocument handlers will have them). Example A-3 shows a cookie being sent in a REDIRECT.

Example A-3. redirect_cookie.pl

use Apache::Constants qw(REDIRECT OK);
my $r = shift;
# prepare the cookie in $cookie
$r->err_headers_out->add('Set-Cookie' => $cookie);
$r->headers_out->set(Location => $location);
$r->status(REDIRECT);
$r->send_http_header;
return OK;