tambien lo podrias hacer sacando primero el total de registros y luego dividir por la cantidad de resultados que te regresa la busqueda, eso te daria el numero de paginas para mostrar, entonces ahi te puedes ir manejando con los numeros de pagina e ir usando LIMIT en la conmsulta para recorrer el recordset que te devuelve.
tambien podrias examinar otros codigos por ahi, hay hartos ejemplos de paginados por ahi
saludos