Куки хранятся у пользователя, сессии - на сервере.
Сессии, вроде как, хранятся в файлах в папке tmp/ с именем sess_идентификатор.
Юзер заходит на сайт, если механизм сессии не получает идентификатор сессии (32 символа по умолчанию =)), то создает для него файл) и посылает ему куки с именем 'имя сессии' и значением - идентификатором. Либо, если идентификатор есть, открывает файл и извлекает переменные. Когда скрипт записывает в сессию переменные, то они записываются в этот файл.