A que le llamas paginar? si te refieres a mostrar una cierta cantidad de registros por pagina y al pie colocar un boton de siguiente,anterior,etc... Lo que ebes hacer es, cuando ejecutes el select * from mitabla agregar al final el comando LIMIT 0,10 (para 10 por pagina) y luego ir sumando 10, LIMIT 0+10,10+10... asi traera solo 10 registros por pagina... espero te sirva...
Suerte
Joe