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.