One way to do it is to use a database to store the results of the query (you could also use that to cache queries - faster for often repeated queries - if your database does not support that) see this pseudocode:

1. Get result of select distinct id from table where QUERY
2. store the IDs (probably separated by commas, or another delimiterm as well as QUERY, and number of results in a database table);
3. To display a page, split the delimited results and use an array slice and just query the database for the rest of the fields for the IDs in the current page (where id in (xx,yy,zz,...etc.) ).

This would only be good for small result sets... I don't even recommend showing search that has more than 10-20 pages ... I would probably display a message at the last page saying that there are a lot of results, and ask the user to narrow down the query.