Prepend custom post type to title?

Is there some way to modify the title on a custom post type?

I’ve got a custom post type called “Library.” What I want to do is to have the title of each page of that custom post type be something like “Library: Accounting.”

I’ve managed to do this when the page itself is viewed by adding appropriate code to the header.php file (to change the <title> tag). I’ve also edited the content-single.php file so that the title shown on the top of the page is “Library: Accounting,” with the word Library being a link up to the archive page for all Library pages. However, the title shown on my category and tag pages, as a result of a search, or via the nrelate Most Popular plugin is still just “Accounting.” Is there a way to change the title globally?