Lo que debe estar antes de tu encabezado "HTML" .. mejor dicho de cualquier otra salida hacia el clientes es -sólo- la función de inicio de uso de sesiones: session_start()
Es decir ..
Código PHP:
<?
session_start();
?>
<html>
etc .. HTML
<?
$_SESSION['variable']="valor";
?>
</html>
Un saludo,