||At the risk of exposing my ignorance, I'll share a bit of what I've learned. I've made occasional forays into the help systems, but mostly I've learned by poking around at buttons randomly until either I get the output I want or the software chokes and crashes.
I've been successful in making some nice enhancements in Photoshop , and have been using that to "pretty up" some maps (see the attached .jpg for an excerpt from a map I'm working on now). I usually start by exporting the layout, with just a few base layers turned on, as an EPS. Successive layers can be added to the photoshop file by turning them on in the ArcMap layout, then exporting again as an EPS, and then using a File/Place in Photoshop to align it with the previous layers. The individual layers can then be modified.
The disadvantage of Photoshop is that everything is done in raster, and you can never get as fine a line as you can with a vector file, like Illustrator uses. Also, you can't really modify individual features very easily without some creative selecting (which Photoshop actually does pretty nicely).
In Illustrator, the main advantages are that everything is done in vector, so lines and edges will be crisp at any resolution or scale. Also, when you export directly from ArcMap to an .ai file, you keep all your features as individual entities that can be edited. While this adds enormous flexibility and power in editing, especially for things like labels, it also adds enormous complexity, almost too much. I've just acquired Illustrator and so have not yet found all the ways to make it do what I want, though I have found several ways to make it crash.
As for tutorials for using these products in map making, I've been looking too, but I haven't stumbled on any yet.
I'm hoping to see this thread get some traffic, I'd sure like to learn more about this myself.