Set the cookie (which sends a header, IIRC), then print a blank page with a meta refresh tag, using the redirect url and a short (1 second may be the smallest increment) refresh time.
or..
Set the cookie, then use something like LWP::Simple to get the contents of the redirected page and print that. One caveat though, if the redirected site isn't your own, they may not appreciate this (though I assume if you're redirecting to another site, you're probably the owner of the other site as well).