Todas las lineas que mandan cabeceras (header(), set_cookie(), session_start()) deben de ser llamadas antes de cualquier código de salida ya sea HTML u otro tipo ya que estas deben de enviarse al navegador como parte de la cabecera del documento.
Un request HTTP se compone de lo siguiente:
Código:
REQUEST_HTTP
CABECERAS (cookies, redirects, etc)
BODY
// Aca va todo el HTML
Por ejemplo:
Código:
HTTP/1.0 200 OK
Date: Fri, 31 Dec 1999 23:59:59 GMT
Content-Type: text/html
Content-Length: 1354
<html>
<body>
<h1>hi!</h1>
.
.
.
</body>
</html>
Si tu envias un header() (cabecera) dentro del body, el navegador ya no la va a interpretar y por tanto va a fallar, es por eso que PHP te da ese error, para que prevengas eso y mejor mandes las cabeceras donde deben de ir (antes de la salida al browser).
Si te interesa conocer más te recomiendo esta lectura:
http://www.jmarshall.com/easy/http/
Saludos.