Look at the Atom Feed Paging and Archiving RFC: http://tools.ietf.org/html/rfc5005 and also look at AtomPub itself (RFC5023).
You should be able to easily leverage that in your project.
Regarding theory: the API is RESTful if the media type of the representation (or some orthogonal specification - see below) tells the client where to find the paging links or how to construct them.
In the case of RFC5005 a number of link relations are defined (next,prev...) that are of course orthogonal to any media type. You find these link rels also in the IANA Link Relations Registry at http://www.iana.org/assignments/link-relations/link-relations.xml
Jan