Buscador con paginacion

[Ronruby]

No seria muy recomendado hacerlo con SESSION ... pero aqui te va:
En la primera linea de codigo pones:
session_start(); //para iniciar la sesion

Luego le asignas el valor de busqueda a una variable de session:
$_SESSION['busqueda'] = $_POST['busqueda'];

Para llamar la variable en otra pagina, tienes siempre que iniciar la sesion, llamarla con $_SESSION['busqueda'] y ya esta.
Y para destruirla:
session_destroy();

Pero eso seria un problema para un sistema de busqueda.

Te recomiendo trates de hacerlo funcionar con GET.
Solo asegurate de que la variable de el GET este en todas los links de la paginacion para que no se pierda al pasar de pagina.