I'm a pretty simple person when it comes to my hats. I either wear a baseball cap with that nasty little button on top removed or a simple boonie cap. A couple of my older boonie caps had a map pocket sewn into the top, but I rarely carry anything up there (especially in the summer). I've carried a bandana up there before and a cloth (or silk) map fits well but a papermap is typically too bulky and just gets soaked with sweat.

If anyone knows where cloth maps can be found for the southwest...