As far as where to store the information about how far along through the list the user was, I generally prefer to put it in the next/previous links themselves as a query string argument. I usually also put in an option for how many to show per page, and since you want the user to be able to change that partway through, it implies that the where-to-start argument should be based on the actual position in the list, not the number of pages.

The hard part relates to the design of how you're going to order (sort) the records. In particular, there are significant performance benefits if you can get the query to only return the records you actually want, rather than having it return all of them and then throwing out the irrelevant ones in program logic. However, that requires that some knowledge of the order you are using be put into the SQL, not just in terms of an ORDER BY clause but also in terms of constructing a WHERE clause to only grab the records you want. (If your SQL dialect supports things like SELECT TOP 50 then the WHERE clause only has to tell it where to start.) This is generally straightforward for a specific table where you know your data, but doing it in a general way is a more interesting exercise. One supposes your query will have to have a field name interpolated at prepare time, and then of course you'll bind a value at execute time. The value can be one of the query arguments contained in the next/previous links, but the field name has to come from somewhere as well, and you may want to pre-select it (or at least pre-select a default for it) and store that in some configuration file.