Si quieres ocultar las variables de búsqueda yo lo que hago es guardarlas como variables de sesión y luego las recupero para la paginación.
Si te da igual, al paginar puedes recuperar las variables de búsqueda con $_GET
el link de paginación sería así:
Código HTML:
<a href="resultados.php?pagina=<?=$pagina+1?>&buscar=<?=$palabra?>">Siguiente</a>
y al volver a hacer el query recuperas con get
Código PHP:
$palabra=$_GET['buscar'];
No se si me explico...
Un saludo