The first licensed maps would have been the ones in Franz Joseph's
Technical Manual. Those maps are largely ignored now, but were popular throughout the 70s.
Star Trek Maps was next, but like
@Therin of Andor mentioned, was actually hard to come by, I only ever saw it once in a book store and never again. The Star Trek Role Playing Game of the early/mid 80s had the next licensed map, it was largely based on
Maps. That game was pretty popular at the time and a lot of the world building was incorporated into other licensed products and fanon stuff.
The first "canonical" map was introduced in "Conspiracy", I think it was used a couple of more times but isn't compatible with later episodes so it was dropped. The TNG art department drew up a new map which started to be used more frequently, presumably it's reproduced in some of the licensed products from the 90s, but I don't have them handy at the moment to dig through. This map's most prominent appearance was probably in "The Chase". It was a "galactic scale" map and didn't show much fine detail.
The later
Star Charts/
Cartography maps provided the fine scale details, and while not entirely canonized, portions have been used for
Into Darkness and in the Kurtzman shows.