Cita:
Iniciado por NueveReinas 
Entonces, ¿va pre-
doctype o algo así?
Antes de todo.
Ni siquiera pienses en HTML, porque eso te confunde más.
Primero debes aprender cómo funciona HTTP, básicamente se trata de cabeceras y cuerpo.
En las cabeceras va información como las cookies que son utilizadas para la sesión, y claro, en el cuerpo puede ir cualquier cosa: datos binarios, html, json, etc.
El tema es que session_start() debe usarse antes de comenzar a enviar el cuerpo de la petición.
¿Ya se entiende mejor?