Lo mejor por tiempo y para que entiendas básicamente lo de AJAX es que hagas algo así:
buscador.php, este recibe las variables y crea el HTML (<table>), y el paginador, como si fuera una pagina independiente, solo limitate a generar el bloque de la tabla y el paginador, no toda la estructura HTML (con <html><head>, etc), solamente por ejemplo tu buscador.php te devuelve algo asi:
Código html:
Ver original <a href="javascript:getPagina(1);">Primero
</a> <a herf="javascript:getPagina(1);">1
</a> <a herf="javascript:getPagina(2);">2
</a> <a herf="javascript:getPagina(3);">3
</a> <a herf="javascript:getPagina(3);">Ultimo
</a>
Eso ya es la estructura HTML lista para insertarla en index.php donde el div contenido este, luego creas una función en Javascript que via AJAX enviandole el parámetro de getPagina() este vaya a buscador.php y cree la tabla con los links directamente.
Como ves son solo 3 archivos:
buscador.php - Recibe, procesa, arma el html, y crea los links
index.php - pagina principal donde se muestran los resultados
ajax.js - Código de AJAX para paginar.
Aunque en lugar de usar ajax.js te recomendaría usar JQuery como te indico pateketrueke.
Saludos.