In a practical world of limits, I would page on the server side to conserve all the resources associated with sending the data. Also, the server needs to protect itself from a malicious/malfunctioning client asking for a HUGE page.
Once that code is happily chugging along, I would add "smarts" to the client to get the "next" and "previous" page and hold that in memory. When the user pages to the next page, update your cache.
If the client software does this sort of page caching, do consider how fast your data ages (is likely to change) and if you should check that your cached page of data is still valid. Maybe re-request it if it ages more than 2 minutes. Maybe have a "dirty" flag in it. Something like that. Hope you find this helpful. :)