There will also be session data stored (a file, or a db record) which would have to be read into memory when the session is started. A session ID would also be sent out to the client so that they can maintain their end of the session.
If sessions are being used in one part of the site, and the user is still of the school to disallow cookies, the session ID is embedded in the URL. On any page that doesn't use sessions, that ID will not appear, and the session will be lost. They won't like it if visiting certain parts of the site causes it to forget about them.