If your query will produce a very small amount of data you can consider to cache the results. But think about this:
- High performance pagination isn't trivial. It can be done database-side with better performance (if you're using Microsoft SQL Server 2012 it has its own extensions for this).
- Pagination is done by users and they need time to read data and click the "Next page" button. Performance hit of a new query won't be big and the database will handle its own cache better than what we can do.
- Cache a large amount of data is useless, memory consuming and less efficient than a new query.
Then my answer is run the query every time. Your database will handle that better than you and it'll scale with your data (otherwise what may work for 500 record will be broken when your system will have 1000000 records).
To summarize: database engines are more efficient than us to cache data and they scale better, (usually) a good index is all they need to perform well.