There is a template for the pagination bar (templates/base/paginate.tmpl). However, this template is not used in all templates that use a pagination.

The HTML structure is the same. The only difference is the additional URL params used for the pagination links. The pagination template should be adjusted to be able to configure these URL params and be used on all templates that use pagination.