Deberías indicar de que "BBDD" hablamos .. no será la misma solución para Mysql que para MS SQL Server por ejemplo u otros motores de BBDD.
"Supongo" que usaras Msyql (confirmalo mejor tu). Si es así .. un ejemplo completo de paginación con "anterior y siguiente":
http://www.devshed.com/c/a/PHP/Previ...th-PHP-part-1/
Un saludo,