make sure your icloud email account is setup as well...even if you don't use it for email. I'm not 100%, but I'm pretty sure it uses the email infrastructure to sync your notes.
From what I can tell, if you look in notes you will have two groups. In iCloud and On This iPhone (device). There doesn't appear to be a way to move the notes on a device into iCloud.
I am not sure if that should be a feature request or not.