First of all, as you are 'complaining' about messy URL's, look at the PHP manual, read about sessions. they let you store PHP variables on the serverside and link them to a specific website visitor. very usefull.
Second, there is an article about pagination here:
http://www.phpbuilder.com/columns/rod20000221.php3
the main thing is that Most databases, like MySQL and PostgreSQL let you LIMIT the amount of records returned, based on an offset and a length.
For example:
SELECT * FROM table LIMIT 24,10
will fetch 10 results starting from the 24th result.
This way you can run the same query over and over, and use the offset ad length to get different 'pages' of results.
if you have 20 results per page, and you want to get the 6th page:
SELECT FROM table LIMIT (6-1)20,20
(6-1 because the first page starts at zero, not at 20)