Se trata de un script ya hecho para estos menesteres, es muy extenso y no deja ponerlo por su numero elevado de caracteres.
Lo puedes bajar desde aqui:
http://jpinedo.webcindario.com/scripts/paginator/
Solo hay que incluirlo en tu script de busqueda y ya está, dandole valor a la variable de busqueda.