Es facil, digamos que tienes 80 entradas o registros.
Haces una consulta mysql para obtener este total (con mysql_num_rows())
Después si quieres paginar por cada 5 entradas o registros, tendrías que dividir para que te dieran las entradas por página.
Por ejemplo, la página 1, tendría las entradas de la 0 a la 4, la página 2 de la 5 a 9, etc.