Es un tema muy comun y hay muchos tutoriales al respecto. Seguro cualquira de esos tutoriales te informara bastante bien como se debe hacer.
paginacion
Y alguien que hizo algo para que sea mas facil paginar:
http://jpinedo.webcindario.com/scripts/paginator/
Saludos.