Notes backup

Go to icloud.com from a Mac or PC and sign in with your iCloud / Apple ID and go to Notes. All your notes should be there.

 

Also, for the future, they SHOULD be stored in your backup. I'm not sure what went wrong. It may be worth restoring again just to see if it works the second time.

(Anyone else: I'm not wrong, am I? Anyone else know if Notes are excluded from the backup for some reason? I can't imagine why they would be.)

 

Check settings / notes / default Account

 

My notes always have come back. Check out Evernote too sounds like it could be of use to you.

 

To user Small White Car: Notes are definitely included in the backup, at least in iOS 6.1. Yesterday, my iPhone 5 was replaced because of a defective camera. When I did "Restore from backup" onto my new iPhone, all of my notes magically appeared.

You could try restoring from backup again.

The backup itself is located here:

~/Library/Application Support/MobileSync/Backup/

However, everything has incomprehensible hexadecimal names, so I don't know how to find just the notes. Maybe you could try searching that folder for some text that you remember was in a note?