Se ti crei tu un id di sessione, per esempio

$_SESSION['id']=md5(time())

e controlli se $_SESSION['id'] è presente, se è presente vuol dire che sta navigando, se non è presente è entrato per la prima volta