Graph paper, some space for notes and (in MM2) the cartography skill.

Don't forget some events only activate, and some messages and entrances are only seen, if you face the right direction. Also in MM2 random encounters are checked each time you turn, not only when you move. In MM1 this only applies at sea for some reason.

I also hand-drew my maps. The most important thing to know is the general layout of a map... they are on 16x16 square grids, numbered 0-15 in both X and Y. When you cast your "location" spell, it tells you where you are on the grid (for example, "(0,6)" as well as what direction you're facing. With that spell you'll know where to start drawing your map. Use it often, as sometimes you'll encounter magical traps designed to disorient you.

And definitely leave space for notes, or take notes on a separate page. You'll want to mark down special locations, secret doors, spaces where there are automatic battles, etc. And use a pencil, so you can erase any mistakes you make!

You might wish to use a few different colors too as sometimes there are different kinds of walls. In the outdoor areas of MM1, there are "walls" made of bushes that you can still move through, and others made from trees or mountains that you cannot. You might want to differentiate between mountains and forests (and other kinds of "walls") but you don't have to. I was able to effectively map everything just using pencil without using different colors, but I had to come up with ways to represent some different wall types.

And as PetrusOctavianus said, some things are dependent on which direction you're facing. This is especially important when in the outdoor areas in MM2, which are more open than in MM1 and don't have artificial "walls" like the first game.