I used to carry a little notebook with me, but since it was a separate thing I would often leave it at home. I can fit a pocketmod into my money clip (yes, I use a money clip instead of a wallet. Less bulk = better) and it's pretty much always with me.
The other thing I add to the system is a Pilot G2 mini pen. These are nice because they are about 1/2 the height of a regular pen so they don't bug you when you carry them in your pocket.