I'd have to say sunglasses. I'll put them on top of my hat, and next thing I know they're gone. But like ZZ-Top says, "Go get yourself some cheap sunglasses."
But my best lost gear story is one I posted in a previous thread:
Whilst hitch-hiking from San Diego to NYC, I crawled under the railyard fence in Yuma and hopped a box to Tucson. Well, the railyard in Tucson is not that close to I-10, so I scurried over to the Aviation Bikeway (Tucson is so bike-friendly, great town) to hike my ass into a better part of town. I stopped somewhere on the bikeway to discard a flannel shirt I had destroyed sleeping in a filthy boxcar. I was doing laundry at the Greyhound terminal on Broadway when I remembered that I had put my Navy dog-tags in the front pocket of my flannel for safe-keeping. Thus began one of the strangest legs of my journey.
I know it doesn't qualify for most-often because I only lost my dog tags once, but I like the story.