That's what cookies are for? Why not just store all choices in a cookie and then update the cookie as necessary. That way no matter where they are, their choices are there, their pathways are preserved.
You can detect if a browser doesn't take cookies. Also, the links should still be the same if they click back, because, in most cases the page is rendered from a local cache and not from the server.