Changing message notification

How can I modify the message display from "You have mail!" to "You have a new private message" and "You have unread messages" to "You have # unread messages" where # represents the number of unread messages. I think it will look more appealing that way. I was trying to approach it but I don't see any template files which makes me believe its in the module itself? Please advise.