I'm a total subscriber to LowFi living when it comes to doing information work on the road and on the run. I'd long ago stopped carrying around my PDA for most jaunts around town in favor of a Hipster PDA-type organizer.
For a while I simply carried around a small Moleskin Notebook and a pen. My setup has since evolved to be extremely low-fi. I now carry around the Fischer Space Pen I got for Christmas a few years ago, a Nick(it) wallet I got for free in the goody bag from MAD Museum's Mad About Dance event, and a small stack of index cards.

[click above to see the annotated version on flickr]
Dimensions are 3 7/8" x 5 3/8". Here's the folded and closed view:
Problem is that I often take the pen out and throw it in a bag or something so I find myself on a subway train with an idea, but nothing to write with. Tina pointed to the Inka Pen, which looks perfect.

If I attach it to my keys, I'll never be without it. Sweetness.
UPDATE: There are a good deal of reviews on the Inka on Merlin's 43 Folders. Check them out before you buy. So far it's seeming to me that the Space Pen might still be better and that the Cross Ion might be a viable competitor -- fewer steps to open/use the Ion. Nice to have found some blogger reviews of the Inka before I went out and looked for it. I'll still play with it if I make it to the NYC location that carries it: Art Brown at 2 West 46th St.
Tagzania is very cool. It's a geography-based place manager that funcitons like popular bookmark managers. It allows you to mark geographic locations and tag them. You can then use an intergrated Google Map viewer to view the map or satellite display of the location. For an example, I've just started riding a road bike and tagged the few places I've taken my bike in the past month.
Would be cool if you could save routes. I could save the cycing routes I take on vacation for retrieval on follow up trips or to share with others. A natural progression would be for Tagzania to be merged with or partner with World66 or some other travelog where people could save their travel information.

