How this all works.
Notes uses a subset of email technology to work, much like reminders. This is why both reminders and notes used to be part of the Mail app in previous versions, before they got their dedicated apps. Lets just say they are a "special kind of email" that doesen't get sent out to anyone, but is stored for your future reference.
As such you need an email account that both supports these features and that iCloud can access. You see, when you use your email to register to iCloud you are using it much like on Facebook: you are providing your email, and it will be your "username", but just like Facebook, iCloud doesen't have access to your mails. To do so you need to register your email under "Mail, Contacts & Calendars" in system preferences.
I know it's a bit confusing, but think of it this way: when you register to anything else it asks for an username, a password and an email, no? Apple wants to make it easier for its users to remember their usernames so your email becomes your username. Your email account and iCloud are not linked in any way.
So what does this all mean?
It means that in order to sync your notes you must add your actual email account (gmail, yahoo, exchange, etc) under "Mail, Contacts and Calendars" to give Apple access or create a @me.com account to which Apple will have access.
If you choose the former method it will work given your email provider supports notes.Some users report problems when syncing to macs that are not running Mountain Lion. If both are on Mountain Lion it should be fine though.
If you choose the latter method you will have a new email account, and you will be able to log into iCloud using either your old email or the new one.
Hope it helps! Any questions (I know it can be a bit confusing) feel free to comment.