This has apparently been made much easier in 1.5; the contents of the menu bar are now specified in a MediaWiki: article whose name I don't remember at the moment.
The text which shows up in the menu bar (at left in monobook) may be edited through the wiki itself. What you need to know is the name for each link. To edit the contents, you navigate to the page named MediaWiki:linkname. You will need to be a sysop in order to edit the text. To get a list of links and other text which can be customized, go to Special:Allpages (on the wiki in question), select "MediaWiki" from the "namespaces" drop-down, and press "Go".
- Where does the text for the corresponding pop-up hint come from, and can it be modified?
- Can more links be added to the existing navigation box?
- How do you add another box? (e.g. to have links back to the site of which the wiki is a companion)