I was without my palm when I started GTD, and it's working out so well I don't have any desire to switch.
I use a half size 3 ring binder. It has my calendar and all my categories tabbed, and an in-box folder. I do like the address book better on my palm, but generally I find the paper system much easier to navigate.
Does anyone have any "paper-specific" hints, opinions, etc?