Coloca el codigo que usas para paginar ya que si estas enviando una variable para hacer tus busquedas, esa variable tienes que enviarlo a cada pagina por ejemplo:
Código PHP:
Ver originalindex.php?page=2&variable=tubusqueda
y eso debes construirlo en tu paginado.
Saludos.