Global page navigation accross WordPress MU blogs

Hi, i try to give all my members their own Site / Channel / Blog…. however i want that they can choose from different Themes while they create their new site BUT as they are member i want they all have a Global page navigation that is on the top of EVERY blog see example .

I found this article and understand that i have to hardcode that into each theme individually but i am not that professional… Can anybody help me or recommend me any plugin to achieve that? Thanks a lot in advaced.