Pagination over a constantly changing list is hard. Really hard. In fact it should be one of those computer science problems up there with naming and cache invalidation.
The issue especially surfaces in news sites, like Hacker News. The hierarchy of posts is constantly changing. By the time you click 'next page', page two has an entirely different set of posts. So how do you ensure that the next page contains what the user expects to see?
Paginating on offset is out, since the valid offset is constantly changing. Paginating on a post's date is also out, since HN's sort order is not determined by date, but rather by a dynamic score.
Well one one method is to store every possible sort order in memory. In fact, this is exactly what Hacker News does. When you click 'next page', HN knows what you're expecting to see, because it has the particular sort order you're looking at stored in a closure.
However this is a lot of data. And it only grows. This means that every so often the garbage collector comes through and expires old links. And old can mean a couple of minutes - far too quick for practical pagination in my opinion.
Send the server the IDs of the posts you already have when paginating. Sort posts by score, limit to your pagination offset, and omit those supplied IDs from the returned collection.
In other words I send an array containing all the previously fetched post IDs as a parameter whenever I'm fetching more paginated posts. Then I make sure that any posts fetched from the DB aren't referenced in those IDs.
That's a pretty pragmatic solution, that in my opinion draws the right compromises. Since I'm paginating via infinite scrolling, rather than links, users won't notice ugly post IDs in the URLs. And since I'm keeping the list current using a stream of realtime updates from the server, posts are unlikely to be out of order. All in all, I'm pretty happy with the approach.