Making an override for the pagination in Joomla 1.6 is almost as easy as working with other overrides. Sadly the new Beez template doesn't include an override for you to copy and use as a base so you have to create your own from the pagination file, which can be a little tricky at the beginning. To do this copy root/libraries/joomla/html/pagination.php to root/templates/your_template/html/pagination.php.
This file contains a php class. You can't redefine that class from the override so you need to delete the class and leave only the functions. When deleting the class you also have to delete the protected definitions. Finally, you need to add the pagination prefix to the function. You probably only want to edit the _list render function, which is one of the few that actually produces some HTML markup. If that's the case you can delete the other functions. The image below shows the changes:

Now Joomla will use your functions for the pagination.
Note that the pagination file actually has code for other elements such as the input limit box but you can only override the pagination. This is because the function that renders the links checks for an override in line 270. Then it checks for the functions inside the file and uses them if found. Sadly the other functions don't have this feature.

works perfectly for joomla 2.5.4! file location root/libraries/joomla/html/pagnation.php thanks for post!
@Tomàs Glad to hear that. We actually wrote it after looking for documentation ourselves and finding nothing ^^
Thanks a lot!!
I was going mad about this.
I couldn't find any doc about pagination layout overrides in Joomla!2.5 until I found your post!
For a while I even thought Google was fooling me! You saved my day, guy!
Thanks a lot!
@Greg In the template's html folder. It's in the first paragraph of the article. The beauty of overrides is not having to change the core files.
Hi, after you create the new pagination.php files, does it go into the template's html folder or does it replace the pagination.php file that is in the libraries folder.
Hi, what exactly was the problem? We're currently working to update the website. When the upgrade is up we'll write an article about how to add the links.
Thanks for the information about adding the head link. However, I couldn't execute the pagination code.
Hey, forget the last comment, I did not really read the article and thought the rel attribute was for the links. However it's a head tag so you should be able to add it from the component overrides. For example you can open the override for the blog, add some conditionals to check for previous/next pages and add the respective links using addHeadLink( http://docs.joomla.org/JDocumentHTML/addHeadLink ).
Well since you have an array with the markup for the link you can't just paste it in. You could try splitting the code in $list['next']['data'], adding the rel attribute and then combining the parts again. The explode and implode php functions should be able to achieve this. That's the solution that comes to mind, maybe someone else thinks of a better one ;) .
Do you know how to add 'link=rel next and rel prev' for blog pagination in the header according to Google's new hint's:
http://googlewebmastercentral.blogspot.com/2011/09/pagination-with-relnext-and-relprev.html