El 'principio sagrado' en este problema es: NADA puede enviarse antes de enviar cabeceras (o cookies, o sesiones).
Lo ideal es hacer todo aquello que necesite enviar cabeceras ANTES que cualquier otra cosa. Si no es posible, hay que guardar la salida en una variable y mostrarla donde corresponda, o usar ob_start()
No sé qué forma te sirva mejor, pero el 'principio sagrado' es inapelable
Saludos