I'm at work right now so I'll be brief for the moment.
I think the tools used vary from people to people, so I can only answer for myself.
In terms of emulators, I stick with the following:
NES: FCE Ultra, if only because it's the most stable on my computer. It has the nifty option of being able to display simply the sprites or the background.
SNES: ZSnes, if only because it's the one I've always used. I've only ever mapped one game (which is still unfinished) with it so I can't really claim it's the best for mapping.
Genesis: Gens, with the KMod fan module, which adds the ability to turn on and off the various display layers, so I can capture only the sprites or the foreground or whatever else I want separately.
GBA: VisualBoyAdvance, no contest. It has tons of debugging functions which make mapping a lot easier. You can turn off any of the 8 graphic layers, and it has two tools I like very much: the Map Browser which allows me to capture the contain of the graphic buffer for all 4 main map layers, and the OAM viewer I think it's called, which allows me to see (and save) all of the separate sprites currently in memory. Those two tools are invaluable in my Metroid Fusion map project. Also, it's possible to advance one frame at a time which helps in making sure that I always keep animated tiles consistent.
As for the actual assembly, I use MSPaint, and I frankly find it a lot easier and faster to use than anything fancier like Paint Shop Pro or Photoshop.
I use Irfanview to cycle through the various screenshots I've made and simply copy/paste each one in MSPaint, removing the background color if I can and assembling them together. Sometimes, I'll assemble both the foreground (actual stage) and background (fancy image in the back) separately and put the first over the second once I'm done.
Sometimes I'll use Paint Shop Pro if I need to do some transparencies because it features layers. I'll paste the segment, add in a layer with the element like water or fog, adjust the opacity, merge them and copy the result in Paint for assembly.
I'll also use Vicman's Photo Editor (rather obscure program) if I need to remove colors to separate a sprite from the background. I know that Paint Shop Pro can do it, but it's a lot harder to use in terms of interface, while Vicman's software is just a matter of clicking on colors.
As for scaling, the general consensus here is that if you're doing screenshot maps, you do *not* shrink or enlarge the maps as it changes the pixels and thus its authenticity.
Some people will add in guides and map keys, but I almost never do. It's mostly because I suck at writing strategies and because I find my page compositing skills atrocious.
Sorry, that's all I have time to write right now.
---
"With the first link, the chain is forged. The first speech censored, the first thought forbidden, the first freedom denied, chains us all irrevocably." [...] The first time any man's freedom is trodden on, we're all damaged. - Captain Jean-Luc Picard
B*tch, meet reality. Reality, meet b*tch. - Me