I write on my maps; here's how:
For long treks, I usually create custom maps (with NG Topo!). I first import them into Photoshop and adjust the levels to make the colors and countours "pop" a little. Then, I add a box of semi-transparent "whitespace" to the map in a noncritical location that I'm pretty sure I won't be navigating through. That box becomes my journal for the day. Each map usually represents "one day" of trekking (~20 miles). Towards the end, as mileage increases, I will have two maps per day.
I size my maps for an edge-to-edge dimension of ~11" x ~11"*, print maps on double sided paper and order them numerically, e.g., Day 1, Day 2, Day 3a, Day 3b, etc.
* Sized so they fit into a 12x12 Aloksak with one/both map views available without opening the bag.
The maps usually get printed on regular copy paper (light!). If I'm going with heavy waterproof papers (like the plastic stuff from Nat Geo), I have a writing challenge: most writing implements smear on the plastic type papers. This bites for journaling and writing navigation notations.
I like the Rite in the Rain paper for writing, but for map printing, it's expensive and heavy. So, I like regular copy paper: cheap and light. When I'm done printing, I usually go one step further, hang the maps from a clothesline, and spray them with Rain-X or Scotchguard.
I keep my maps handy, and then write things throughout the day on the neat little half transparent boxes that I photoshopped into the map image.
Sometimes, if I can spare the weight, I'll add a tiny notebook to the mix, mainly for writing non-route-related things in camp (like comments on why a particular piece of gear wasn't working, or a shopping list for the next trip, or just to solve some DE's here and there for mental stimulation <-- "geek!"). When I take a notebook, I use a Rite in the Rain #391-M mini notebook, sold here at BPL <-- "pimp!"). BUT I also really like a little floppy Moleskine, which is about the same thickness and a little bigger, because the writing paper is nicer and it has a little pocket in the back I can use to stow a leaf or flower petal or a laminated index card that contains key phone numbers, calling card number, credit card number, resupply logistics info, whatever.
For a writing instrument, I use either the Nalgene waterproof pen, which writes on virtually any surface and bleeds less than sharpies, and a pencil. I like a pencil because I can erase and it works in the rain.
If I am trekking a new off-trail route, I always bring a set of fine point waterproof drafting pens: red, blue, green, and black, for detailed navigation notations. I use the various colors for different types of notations.
I have a short (4") mechanical pencil (0.5mm) that I picked up from somewhere (who knows?) that I really like because it's convenient and stays sharp.
But for nostalgia, I more often just carry a golf pencil or two with an eraser head and sharpen it as I go with a small sharpener.
OK, so what do I write about?
1. Lots of navigation info.
2. Animals I see - but more importantly - the unique behaviors they were exhibiting at the time. On my arctic trek, I noted not just a bear, but the groggy bear that stood up and looked yummily at Roman; or the Jager that dove down and nicked my hat becuase it was defending its nest; or the wolverine that ambled along the river bank, stopped, looked over curiously at us, and then ambled on its way. He had the same voice as Crush the Turtle in Finding Nemo. I wrote that.
3. How my gear is performing, and how it makes me ... f ... f ... feel...
4. Ailments. These are most often about my feet.
5. Unique experiences throughout the day. "High ridgetop winds - hard trekking!" or "Swampy tussocks coming out of XXX basin" or "Found spike camp - log stool was comfy!" etc.
I don't write much polished narrative. Here and there, I will, in order to record the philosophy of the moment, so to speak.
I like journaling a lot. It's a rewarding part of my trekking experience.