Beh... si in effetti ogni pagina che sfrutta le sessioni deve avere session_start();.

Ad ogni modo, filippo.toso ti ha suggerito un ottimo metodo per fare in modo che la sessione sia sempre utilizzabile da tutti i tuoi utenti, anche coloro che hanno disabilitato il salvataggio dei cookies.