I found this paging XSLT example at Nibble's site: http://www.nibble.be/?p=11
But it's a bit nasty to copy-paste the code (a lot of newlines and the quotationmarks are not valid for XSLT (” instead of "). Besides that, this example does not use zero-based pages. So page one will show as "somepage/1", instead of "0". It's easy to modify the XSLT if you want to use "?page=1" instead of "/1".
I modified this XSLT a bit and wanted to share it here.