постраничный вывод делаеться так
ну это я на пальзах объясню)
сначала лимит указываеться. например 20 записей на страницу.
select * from table limit 0,20
здесь 0 это начальная запись, 20 количество(вроди так=))
к скрипту обращаешься чтонить типа
script.php?page=4
тоесть
запрос примет вид
select * from table limit 80,20
4*20
и так далее.
для построения блока ссылок для навигации можно сделать что то вроди
select count(*) from table
полученное значение поделить на 20 и вывести как ссылки, параметром будет номер страницы.
вот тут можешь более подробно и понятно почитать
http://www.codenet.ru/webmast/php/Navigation-Bar/