Hola:
La primera página debería tener una instrucción adicional para saber de cuantas páginas contará la paginación (select count(*)), con el resultado, averiguar el número de páginas que serán y poner por cada página un enlace o botón que normalmente se peticionará por get, así puedes entrar directamente a la página requerida, y esos enlaces serían: enlace.php?pag=n (con n como variable)...
Por último en las consultas añadir una cláusula limit...
"select... limit ".((int) $_GET["pag"] - 1) * $cuantas. " $cuantas";
Saludos
