In this sample, if a map is instantiated with the "hybrid" basemap (imagery and labels), the labels remain when the new basemap is selected from the gallery. If the map is instantiated with the "terrain" basemap (terrain, linework, and labels), the linework and labels remain.
See it in action here: Plunker