Lo puedes hacer con javascript, con lo que tendrías que cargar todos los resultados previamente para paginarlos, lo puedes hacer con Ajax, cargando los elementos a medida que te hagan falta ( al cambiar de página, por ejemplo ) o lo puedes hacer del lado servidor, cargando el contenido de cada página y realizando una petición por esta. ( en ajax no recargarías )
Yo soy partidario de hacerlo del lado servidor, porque? porque cada página tendrá su enlace, podrás validar la página que solicitan, y generarás un link que podrá ser indexado.
Opto por PHP, y si los resultados son dinámicos, los puedes almacenar en una base de datos y mejor que mejor.
http://www.desarrolloweb.com/articulos/1035.php
Un saludo!