Tienes la respuesta en las FAQs de PHP.
Como soy incapaz de poner un link al artículo, lo pego aquí:
Pon antes de enviar ningún caracter ( donde pondrías un header() o una cookie ) el siguiente código:
Código PHP:
<?php
ob_start();
?>
Y al final de todo de tu pagina pon:
Código PHP:
<?php
ob_end_flush();
?>