Con php y mysql tengo que hacer una consulta avanzada y ademas paginarla, ¿Cómo lo hago?

Estoy elaborando una consulta avanzada con php y mysql, ya lo he logrado con un criterio con su respectiva paginación, pero lo que necesito es hacer una búsqueda con varios criterios, el problema es que tengo que hacer múltiples condiciones, por ejemplo, si se cumplen dos criterios de búsqueda haga la consulta y muestre el resultado de forma paginada, si son tres criterios haga la búsqueda de la misma forma, y así sucesivamente, El problema es que al hacer las condiciones no se como hacer que una consulta se mantenga con los mismos criterios, lo he intentado con $_SESSION, $_COOKIE y también con los métodos $POST GET Y REQUEST.

he logrado hacer que me muestre los resultados de la primera pagina, pero si voy a la segunda, se pierden los criterios de búsqueda.

Espero haber sido claro en lo que necesito,

Agradezco me puedan ayudar.