Recovering lost notes on iPhone 4s
If you backup with iTunes and you restored from the backup and the notes were gone, then there is no where to retrieve them from unless you have another backup that contains those notes.

Launch iTunes on the computer and go to iTunes>Preferences>Devices. You will see a window with all of your backups listed in it.

If you see a recent backup that you are certain contains the notes that you need, recover deleted notes from iPhone backup.

If your note is gone from iCloud.com there is only a few ways to possibly recover it.

The first things I would check is a iCloud Backup, a iTunes Backup, or a 3rd party email that may have contained the note. To restore from a iCloud or iTunes backup follow this link. This article explains how to restore a device from either back up.

Note if you have backed up since the note went missing, you will not have the note on the backup. Make sure you do not back up if trying to restore from a back up as this will back up the content without the note.

To get to the "Set up assistant" on an iOS device, you must go to Settings>General>Reset>Erase All Content and Settings. Once the phone restarts, you will be at the "Set up Assistant" 

Gmail emails are very commmon sources for notes and you may have been adding them to the gmail notes without even knowing it.