Si su consulta no devuelve un prohibitivo cantidad de resultados, considere usar Jquery para enviar una página con una función Tablesorter. Toma una tabla HTML formateada correctamente y páginas, géneros, etc. sobre la marcha ... no hay necesidad de variables de consulta adicionales si no lo desea. Es mucho más fácil que utilizar la ruta completa de búsqueda de PHP, y es mucho más rápido para el usuario.
Mi ejemplo favorito es aquí: http://datatables.net/
Se puede no satisfacer plenamente sus necesidades, pero está bien para muchas aplicaciones. Si lo hace, simplemente no olvide formatear su tabla con thead y tbody para que pueda recoger los elementos de la tabla correctamente.
posible duplicado de [paginación MySQL sin doble consulta?] (Http://stackoverflow.com/questions/818567/mysql-pagination-without-double-querying) –