Cookies were never the only way to do this. Before cookies became popular having the ability to create a session was still possible. The primary method of doing this was similar to cookies, have a sessionId parameter to your query. There were also passive ways of profiling a user's client to isolate it based on what it looked like (IP, User Agent, user agent Accept and Accept Charset, etc see [0]).

[0] http://www.rkeene.org/viewer/tmp/wwwftp_cgi.c.htm#line182