If you're in the main notes window hit the back arrow top left, this takes you to the folder selection window, one of which is 'recently deleted' so if you have deleted them you'll find them there, you'll also be able to see if you have accidentally switched folder and they're all happily stored elsewhere. Also, check in the settings app in the iCloud section that you have it switched on for notes. In addition, if you fon't have that much stored on your phone you can (from iTunes) set it to backup to the cloud so you don't have to worry about backing up to iTunes.