Pens, letter opener, and scissors are in a pencil jar on my desk. Scratch pads are in a mesh file holder, along with my (paper) planning calendar and a few pages of commonly used reference information.
I don't have a rolodex, as I file all contacts electronically and then throw the physical cards away.
Tape, stapler, post-it notes, paper clips, etc. are in my desk drawer. There's also a small supply of file folders, mailing envelopes, and so forth on a shelf to the right of the desk.
All other office supplies are in a storage closet. The basic idea is that the more often I use something, the closer it should be.