Mix. From a realism perspective, I think the player would know that the cities were there to begin with, and could fast travel to them. Plus, what if somebody wants to roleplay a native Nord? They'd know the routes between cities.
However, I wouldn't mind if the cities were ON the map (Oblivion hand-drawn style) from the start, but you couldn't fast travel until you reached them.
Or, of course, go back to Morrowind style fast travel, of paid fast travel.