You go to phrases in ACP and change the phrase. (ACP > Appearance > Phrases > search phrase)
I don't have Media Gallery but the phrase for navigation will be called something link nav.media
Otherwise I think you can change the actual navigation entry by activating developer mode in config.php but the above is probably the "proper" way to do it.