Let it be known that Microsoft's terrible design of list paging is inexecusable and to make matters worse, the documentation is practically non-existent.  You would think that paging with a SPQuery would be a piece of cake!  I mean, I write paged data queries all the time.

NOT!

Colby Africa has a good overview of the issues and some basics that gave me some good insight into the core issues.  Of course, the difficulty with the SPQuery and paging isn't really with going forward, it's with going backwards.  One MSDN poster suggested storing the previous pages (see the last post here), which when you think about it, isn't a really good solution given the amount of paging strings you'd have to store (you can't just store the last navigation since going "Previous" twice requires going back twice).

Since going forward is the easy part, I won't get into that.  With regards to paging to previous pages, I hacked around a bit and spent a good 2-3 hours trying to deduce how the paging query string worked before I finally figured it out.

The algorithm works like so:

1. When paging FORWARD, capture the ID <AND SORT FIELD VALUE> of the first item on the newly retrieved result collection.
2. When paging BACKWARDS, use the previously captured ID <AND SORT FIELD VALUE> of the first item on the current result collection to generate the paging string.
3. Once paged BACKWARDS, capture the ID <AND SORT FIELD VALUE> of the first item on the loaded page for the next BACKWARDS operation (just leave this off of the input query if going forwards again).

By capture, I mean to store the data and persist the data somehow (perhaps in the ViewState or SessionState).

And there you have it: three simple steps

As an example, consider the following data set, sorted by Title:

ID		TITLE
---------------------------PAGE 1
17		Apple
21		Banana
18		Currant
---------------------------PAGE 2
19		Durian
5		Elderberry
1		Fig
---------------------------PAGE 3
7		Guava
10		Honey Dew
12		Indian Gooseberry

Consider a scenario where we're building a web application.  After the result set for page 3 of the data is loaded, I want to capture three pieces of data if I want to be able to load the previous page:

1. The value of the ID of the FIRST item on the page
2. The value of the TITLE of the FIRST item on the page (or whatever field you are sorting on)
3. The PagingInfo string after the query is executed

The PagingInfo is already set for paging foward again.  When I page backwards, I will need to generate a new query using the PagingInfo.  To do so, I will need to:

1. Replace the p_ID and set it to p_ID=7
2. Replace the p_Title and set it to p_Title=Guava (replace p_Title with the static name of your sort field)
3. Add two parameters:
   1. PagedPrev=TRUE
   2. PageLastRow=6 (last index of the second page, where we're going - this is easily calculated if you know your page size and your current page (keep these in the ViewState))

I used the following two regular expression patterns:

Regex _pidPattern = new Regex("p_ID=(?'pid'\\d+)");
Regex _pTitlePattern = new Regex("p_Title=[^&]+");

To replace the values in the string like so:

pagingInfo = _pidPattern.Replace(pagingInfo, 
	string.Format("p_ID={0}", firstItemId));
pagingInfo = _pTitlePattern.Replace(pagingInfo, 
	string.Format("p_Title={0}", firstTitle));

In this case, if I'm on page 3, the string for going back to page 2 should be:

Paged=TRUE&PagedPrev=TRUE&p_ID=7&p_Title=Guava&PageLastRow=6

And once I'm on page 2, the string required to go back to page 1 should be:

Paged=TRUE&PagedPrev=TRUE&p_ID=19&p_Title=Durian&PageLastRow=3

Well, actually, you don't need the string to go back to page 1; but this is just to give you the general idea.  In summary, the trick is pretty simple: you always need to store the PageInfo string for paging SharePoint queries and when you retrieve a resultset, you want to capture the ID and sort field of the first item.  When you go forward, the PageInfo string is enough.  When you go backwards, you need to use the captured pieces of info.

Hope that this has shed some light on the otherwise nebulous paging functionality with SharePoint list queries!