Okay, I enabled Notes for my gmail account in the Mail prefs pane. Went back to the iCloud pane, and it still told me I need an icloud address.
Sorry, I should have clarified: once you enabled notes syncing for a GMail account, you have notes that sync through that GMail account. It's completely separate from iCloud notes. I guess you could think of the iCloud notes option as being similar to the GMail notes, but for an iCloud account.
Think of it as two separate services, iCloud and GMail.
Okay, fine, I'll just open up Notes. It hits Little Snitch asking to connect to a gmail server, a good sign, so I allow. It says "Updating", and finishes with no content.
This is where it gets fun. The reason why nothing happened is because right now your notes on your phone are probably stored locally, because you didn't have any note-sharing enabled before (whether through GMail or iCloud). There should be a way to shift the notes over to your GMail account, but you would need to do it note by note. I'm not sure if iOS 6 changed this so that you can shift multiple notes at once. I can't guide you on this one because I switched myself over to only having one account that syncs notes (iCloud), for reasons I'll describe later.
On your computer's side, you'll need to make sure that you have notes enabled for the correct account, too. I'm assuming you're on OS X 10.8; go to the System Preferences, then "Mail, Contacts, and Calendars" settings. Select your Gmail account (or if you're like me and have more than one, the one(s) that you want to sync notes through). Ensure that notes are enabled for syncing. The account(s) that you're using to sync notes with on your phone must be the same as the one(s) you're using on your computer, otherwise the notes will be sent to GMail but the other device won't see them.
If you want my opinion, it's a big pain to have notes syncing between multiple accounts. Even though I thought I had specified what account was the default, I would have notes being created across multiple accounts. They synced between my devices just fine, but they were originating from different accounts. It was pretty annoying.
My suggestion would be to just make the @me or @icloud account. There's no guarantee that Apple will continue to support note syncing through GMail now that they have it through iCloud, and my guess is that any new features regarding notes will only be applied to syncing through iCloud.
I don't understand why Notes are still attached to e-mail accounts. They should just be documents stored on your iCloud space.
I agree. It seems that they've just taken the framework that they had for syncing notes through GMail and applied it to their own email service. Maybe in the future it will work differently.