Lorenzo Alberton has posted a tutorial today about using teh PEAR::Pager package to create "pretty links" with a little help from mod_rewrite.
Most PHP pager classes can work just fine with GET parameters, correctly forwarding them through the pages. Few of them let you control the navigation links they create, though. This can be particularly annoying when you have some nice urls (thanks to some mod_rewrite rules o to your hand-crafted front controller) and the pager class can't respect them, showing the real, ugly links to the world.
If the above scenario is not new to you, then you should probably have a look at PEAR::Pager. It's a fully customizable package that should satisfy all your needs, including your preferred link format.
In his examples, he provides the mod_rewrite rules to use, a sample PHP script that would normally use the $_GET values (in an ugly URL) to paginate the results. He also compensates for if the page number is actually a part of the path and not just at the end of the file name.