Hola,
Exactamente no se puede mandar SALIDA al navegador antes de un header() o un setcookie() (realmente el setcookie() genera una cabecera que podrias crear con header()).
Asi que el orden podria ser:
Código PHP:
setcookie(....);
header("Location: ....");
exit;
Saludos.