Recently came accros with the request for paging in a Content Query WebPart, because reinveing the wheel is a waiste of time. I ended bumping into this interesting webpart: Enhanced Content Query Web Part.
I ended up needing to customize some code, change the Pager webpart XSL and apply some CSS as well. But Worked beautifully after deployed & implemented.
If you want to read more general information; http://blog.mastykarz.nl/paging-content-query-web-part/.
Good Luck!