Hola
Pude ser tan facil como dice emilio o tan complicado como lo veo yo:
1. Debes controlar el número máximo y mínimo de páginas.
2. Si lo que realizas es una busqueda debes poder mantener las condiciones de búsqueda en las diferentes páginas.
3. Debes crear una barra de navegación, por ejemplo con los botones PRIMERO, ANTERIOR, SIGUIENTE, ÚLTIMO.
Y seguramente con esto me quedo corto.
PD. En esta direccion
http://jpinedo.webcindario.com/scripts/paginator/ puedes econtrar un paginador para MySQL, no creo que sea muy complicado convertirlo a culaquier tipo de base de datos.