Notes syncing is flawed but still possible
I spent about 25 minutes with an Apple tech support person and he was both friendly and useless. Didn't have a clue about Notes syncing, but I did find out the answers online.
The fact that Apple has forced its customers to use iCloud for Notes syncing and intentionally removing syncing ability from iTunes is both ominous and bad service. If it suggests what is coming in the future, complete forced dependence on iCloud I'm ready to run and hide. They could fix this so easily and give back syncing to iTunes.
In Apple's Brave New World, you'll have to check to make sure that on your iPhone Notes are in your iCloud account. There's a little button at the top of the Notes window that says Accounts. And if you've got Notes that you created before setting up iCloud on your iPhone, they will appear under "iPHone" whereas Notes you created after setting up iCloud on your iPhone will appear under "iCloud". Only those notes that you created afterward will appear in iCloud.
You also need to make sure you don't have Notes set up under an IMAP account like Google, as this will conflict.
Another thing to check: can you create Notes in iCloud.com or on your Mac? And if you create them on your Mac, can you then see them on iCloud.com? That's the first thing to check out to make sure your account is working.