Dang, you've prodded my guilt complex! I do keep a notebook in my bag, but don't use it enough.
I'd suggest starting with the basics: date, time, location, lens (if you use more than one), shutter speed, and aperture. As you gain experience you'll probably discover things you want to add on your own. If you use a spot meter you might also want to note the meter reading so you can see how well your choice of exposure worked in relation to the meter reading. In the latter case it might also be a good idea to note the dynamic range of the scene – especially if you're into or planning to get into the zone system.
Now all I need to do is take my own advice ...