OK. Thanks for the feedback perrin. I wasn't sure if there was another way around it if cookies were disabled (other than using a hidden form field - but that would require a form with a submit button on each page, whether a form was already on a page or not...)
The only other way is URL-rewriting. It's a fair amount of work to get right. Apache::ASP does this for you, and some other mod_perl modules too, but I don't know any that do it for CGI.