Segue uma explicação simplificada.
Cookies são armazenados no navegador do usuário. O que você tem no servidor é a sessão, que pode ser autenticada via cookies, pois os valores dos cookies são enviados junto com cada requisição do usuário (seja ao clicar em um link, seja ao preencher e enviar um form).
O que pode estar te confundindo é que nem sessões, nem cookies, dependem de autenticação (login). Você poder ter cookies no cliente, e uma sessão equivalente para ele no servidor sem que ele se conecte de alguma forma, e pode usar essa sessão para rastrear a navegação. Navegue em algum site de vendas (como Amazon) e você notará que as recomendações são com base na sua navegação, mesmo se você não estiver logado (ex: usando uma aba anônima).
As recomendações e histórico também pode ser complementados pelo registro do ip de acesso (nem sempre único a um usuário só) e páginas acessadas a partir desse ip, gravando em um banco de dados. Esse tipo de informação é mais útil para fins estatísticos, pois pode capturar quais produtos um grupo de usuários tem acessado com mais frequência, enquanto que sessões são mais limitadas à um único usuário.
Cookies, sessões e registro da navegação se complementam como ferramentas de recomendação e registro de atividades.
Abraço.
