Las cookies han de crearse antes de mostrar cualquier tipo de código al navegador (cliente). Esto quiere decir que las cookies (así como las redirecciones) han de ir colocadas en el script antes de la apertura de tu etiqueta <html>.
En otras palabras, no se puede imprimir ningún tipo de mensaje ni de etiqueta HTML en el script antes de haber creado las cookies.