Siempre que vayas a usar sesiones, tienes que usar session_start. Por eso, si intentas usar la variable superglobal $_SESSION.
Léete estos links donde viene explicadas algunas cosas:
http://www.php.net/manual/es/function.session-start.php http://www.php.net/manual/es/session.idpassing.php
[EDITO] Tras hacer ciertas pruebas, como decía sólo tienes que usar session_start si vas a usar sesiones y debería funcionar aunque pase por una página que no uses sesiones, a no ser que haya caducado la sesión o tengas las cookies deshabilitadas.