FWIW I'm not suggesting that people do any of this today. But it is how it was actually done - it wasn't the case that advanced web apps that required per-client state management weren't possible at all without cookies.
exactly! web developer in the late 90's did that and worked fine. Yeah it is a bit more pain to use, however it keeps web stateless which was a what it suppose to be. If you want to make your fancy desktop stateful programs do it with something that is not document base like html.
It didn't keep the web stateless, though. It implemented state on top of what we had at the time, with certain flaws that others have already pointed out in this thread.