Make a field which keeps track of "post-date" and use a SQL-query that sorts by it.
$sql = "SELECT * FROM tablename ORDER BY your_date_field desc";
Then I've used a code posted in an article here, which gives you what you want (prev 1 2 3 next and so on), with selectable no_of_entries_per_page-variable.
Check this out:
http://www.phpbuilder.com/columns/rod20001214.php3?page=3
You will have to "integrate" that query in the above code, but that is not so complicated...
Hope this helps. =)
/Anders