Wikipedia:MediaWiki interface messages
All the interface text can be translated trough the MediaWiki namespace special pages; for a full list of messages look at Special:Allmessages
For example to localize "Main Page", go to Special:Allmessages, find the special mediawiki message for it (it is MediaWiki:mainpage), and put the localized value (eg: ᎤᎵᎮᎵᏍᏗ); then the default page is called like that (no more need to make "Main_Page" a redirect) and ᎤᎵᎮᎵᏍᏗ now appear on the navigation box...
Now go and complete all the others :) Maybe MediaWiki:sitetitle and put ᏫᎩᏇᏗᏯ?
NOTE: namespaces themselves (eg: Wikipedia:, Talk:, User:,...) can't be translated that way; you need to contact a developper in order to create a LanguageChr.php file with those if you want namespaces to be localized too.
See also meta:Wikipedia_in_other_languages, and you can complete the text the free encyclopedia in tsalagi, and ask for a localized logo to be made.