I accidentally deleted the Notes app and cannot find it (although when I do a spotlight search it does come up). Any ideas how I restore it to my screen? Thanks!
It sounds like it's not deleted, but just off of the screen. I've had this happen to a few of my apps. What I always do to fix it is go to
Settings > General > Reset > Reset Home Screen Layout. You'll get your Notes app back, but your Home Screen will be arranged into alphabetical order, and unless you're JailBroken, this is pretty much the only way to get it back without restoring.
It's not possible to delete it, as it is one of the built-in apps that you cannot remove. You can, however, move it somewhere daft. If you check in your app folders, and do the press-and-hold to move jiggle, it should show up somewhere, possibly on the mystery last screen.
You aren't close to the app limit by any chance are you?
Have you tried restoring your iPhone?
See http://support.apple.com/kb/HT1414 for the details on how to do this.