First thing : ENABLE THE TERM STORE!
M$ was nice enough to not give us O365 users a way to easily enable the Managed Metadata feature.
These guys resolved that issue with a sandbox solution : http://www.sharepoint-tips.com/2012/02/enabling-managed-metadata-in-office365.html
After you have the Managed Metadata feature enabled, you need to goto the Term Set management tool. But since its O365, you should use the one thats under your Admin dropdown menu
Create your navigation nodes: