use Apache::Constants qw(REDIRECT); # if you don't already have it
sub handler {
  my $r = shift; # normal {grin}
  ...
  if (detect your cookie here) {
    $r->header_out(Location => "http://web.stonehenge.com/perltraining/");
    return REDIRECT;
  }
  ...
}