I prefer providing a "Range" header for pagination. It's typically used for retrieving byte-range chunks of large objects, but it's also applicable to return a subset of a result set, like "Range: records=0-10". This has the drawback of not being easily applied from within a graphical browser, but I don't consider that a big priority for a REST API in the first place. Viva la curl!