If your query does not return a prohibitive amount of results, consider using Jquery to page it with a Tablesorter function. It takes a properly formatted HTML table and pages, sorts, etc on the fly...no need for additional query variables if you don't wish. It's SO much easier than going the full-blown PHP paging route, and is much faster for the user.
My personal favorite example is here: http://datatables.net/
It may not fully suit your needs, but it is cool for many applications. If you do it, just don't forget to format your table with thead and tbody so that it can properly pick up the table elements.