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 http://www.nbc.com .
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.
Steve