Do you get the entire result set (all the pages) in one go, or do you get one page at a time? In any case you should keep a local cache of the data you received from the server and use that when the user navigates the pages. For example, if you retrieve one page at a time, and the user goes from page 1 to page 2, then you need to retrieve page 2 from the server. But if the user now goes back to page 1, then you should load that from the cache. If the user goes to page 3, then you should fetch that from the server and add it to the cache.
Next I would separate the logic for displaying a single page to the user and fetching a page from the server. When the user clicks on the next page button, you should ask the cache object for the next page, but don't return anything. Instead the cache will call a callback function once it has data. If the data is in the cache, it would call the callback function immediately, passing the result as an argument. The callback function would then update the view presented to the user. If the data is not in the cache, an ajax request is made to the server for that data. Once the data is retrieved, the callback function would be called.
I'm usually against using xml with ajax (I prefer ajaj; Asynchronous JavaScript and JSON. It's also a lot more fun to say out loud). JSON is a better alternative, because it's a lot easier to work with in JavaScript, it takes up less space, both in memory and during transport. Since JSON objects are normal JavaScript objects, adding them to a local cache is as easy as concatenating two arrays (the cache you already have and the new elements retrieved from the server).