Without state, a token can be a bookmark into a predefined ordered dataset. That's more reliable than an offset, but just as inflexible, and much more expensive on the server side.
Or, I'm missing something too.
A simple method would be to take the state information the server needs in order to continue the enumeration (e.g. sorting order, how far along it was in the enumeration, etc.), JSON-encode it, encrypt&sign it, and then base64 encode it.
Return that token to the client, and if the client wants more data it can pass that token back to the server, which can decode it into all the information it needs to resume the enumeration.
A relatively simple approach that involves server side state is to periodically (once a minute?) generate the list of (for example) the 10000 top items.
(A high traffic site will most likely want to do this in any case, so that it has a cached list of items ready to serve to clients, instead of issuing a database query to find the top items for every request.)
Now, instead of overwriting the list of top items every time you regenerate it, keep multiple versions of the list. Then you can make the link to the next page specify the version of the list and the page number. That way, users will browse through one specific version of the list.
(This requires storing some state on the server, but the amount is relatively small. You control both the size of the generated list, how often new lists are generated and how long they are kept, so there is an easily calculated upper bound on the amount of state information you need store.)
I can see that the other comments on constructing continuation tokens won't work for HN assuming post upvotes are mutably updated.
