I would recommend that you send your serach request with ajax and have a JSON object returned with a list containing the search hits and some metadata about the search (such as *total_hits* that states how many hits there are available on the server. This number should be equal or greater than the length of hitlist).
GET /search?q=<query>
{'hitlist': [...],
'total_hits': 1234}
The size of the hit-list could be ~3 pages since this is probably the most common hits that the user will see. So for the three first pages you don't need to access the server. This could be done in jQuery on the browser. For more results you could have your server support an optional parameter such as:
GET /search?q=<query>&limit=20,40
The limit syntax could be the same MySQL's, then you could ask for the 10 last too (just remember to take proper precautions when passing those parameters into your database if you use SQL!)
So for the pagination look on the browser you could determine how it should look like from the *total_hits* value. If there are few you don't need pagination and if there are super many you could settle with just a next button. All results could be showed in a and if you want any fancy pagination effects you could take a look at http://sorgalla.com/projects/jcarousel/ .