The site you referenced has removed the nav completly, not what I would do or recommend as several important links like the login/logout, cart, account, etc. appear there at the appropriate times.

To rearrange open a copy of the includes/templates/template_default/tpl_hrader.php file and find the bof and eof for the nav section... you can re-order this as long as you move the complete block before or after another complete block of code - save and upload to your template override folder