So, one of the features I saw from Dragonborn, was not only did we get an entirely new map for Solstheim. But we also gained a quick-travel method on the big maps, back to each Map Location....

So how would we go about doing this?
Would we have to create an entirely new map using Flash somehow? Can it be done entirely within Creationkit? or am I SOL?

The maps aren't made using flash. They are using the lowest level detail Terrain LOD meshes and textures. We have had the ability to make new maps for custom worldspaces since before DB came out.