We have a table with 2 million plus records and we need to paginate through it at 100 records at a time.

What is the best way to approach this while keeping server load and overhead cost down?

Looking for any solution:
different query types
caching
mysql settings
hardware recommendations
indexing