It would be rather neat to zoom in on the paper map and suddenly find your view blocked by clouds. Zooming in further will push your view through the clouds until you have a birds eye view of (stylized) realistic terrain. Clouds are only one method that might work, but I'm sure you guys could think up other methods of transition.
I wouldn't want my view to be obscured at any point while zooming in or out. For one thing, what if I want to zoom out to a level in which there are clouds in my face? Disaster. But potentially even worse is suddenly losing sight of the map would disorienting. You'd have to find points of interest all over again. I'd rather it work just like in GC2; although there is a difference - there wasn't a 3D environment to deal with. Nonetheless a simple fade in/out would suffice for me.
That being said, just having the other world map be burned into the cloth anew would be simple enough and still get the job done. That is how I originally figured it would happen.
I actually think this would be the best way to do it. But rather than having the the maps being 'burned' into the cloth, they should use an ink effect! Have the old map ink dissolve while the new map ink appears, as if seeping into the paper. There's really no need for fancy animations that would be both disruptive and potentially problematic on some systems. Also, having one map fade in while the other fades out would give you a brief moment to view relative positions.
Oh oh - what about being able to overlay one map over another, in different colors? It might be too busy and confusing, though. Maybe you could choose only certain objects to overlay, like I could choose to overlay all settlements, or all units, etc in the Astral Plane over my regular worldmap.