Obviously your map is going to be tied to your setting, so one can inform the other. It's best to decide what kind of sci-fi you want (or its scope) before you start on your map.
Single System FutureIn this type of setting humans haven't traveled far. There might be moon colonies or inhabited asteroids brought into orbit, maybe there is even a colony on Mars. Here you needn't worry about a star map but you should decide how many environments there are, what their purpose is, and what makes them feel different to the players.
The Beginnings of FTLThe next step of Single System Future (and you should start there). The humans have visited a handful of local star systems and established colonies. fairly easy, just pick local stars and give them planets. Again, try to make the locations feel different. Also keep in mind that this setting really lends itself to exploring new worlds. We have the means to reach them but are just now taking those baby steps.
Restricted FTLThis is one of my favorites for space opera/space fantasy. The idea is that we can travel FTL, but we can only jump a specified distance and we need to end that jump in a system. Or FTL is accomplished through gates, leaping from one system gate to another. I like this because your star map now has terrain, or paths. Jumping to a system may require a circuitous path leading through five different systems. It is also the best explanation for why there are still "wild" planets that haven't been charted, as they are out of reach of the current engine technology or gates haven't been established yet. Then during your game if you want to run an exploration session, introduce a new engine or gate that can get the heroes there.
This map is laid out more like a maze with a few nexus points where trade routes converge. Your map could encompass a few worlds or a few hundred. How much work you are willing to get involved with is up to you.
Unrestricted FTL and the Sector CheatUnrestricted FTL means the heroes can jump anywhere, at any time, for any distance. The Last Parsec is a good example of this. In theory the stellar map includes millions of systems... take it easy, don't hyperventilate. Breathe into a bag. We got this. Allow me to introduce you to the Sector Cheat.
The basic idea is that if FTL is so ubiqutous, then it is less likely you will run into "single planet" species, unless they have already been conquered by a spacefaring one. So most species, or at least the strongest ones, will have dominions or Sectors that they control: The Kargan Expanse, The Melatonka Protectorate, etc. Carve up the galaxy into chunks and assign a species to control those areas. Even if they are all a part of the same empire, these sectors will have a drastically different feel under local control. Now that you have those Sectors, write some basic description about how those Sectors operate, what kind of Government do they use, etc. DON'T start sticking planets in them at this point. It is unnecessary. Save that for the adventures.
So let's say you want to do an adventure on an Ice World mining colony, and you want to challenge your players by making it in a very restrictive part of space. Well, the Kargans have strict control so name the planet and drop it in there. Or if you want the same adventure planet in a place full of slaves and corruption, drop it in the Mealtonka Protectorate. The point is to build your planets as you need them and drop them in a Sector that will may make life a little more interesting for your heroes.
The one problem I have with Unrestricted FTL is that there isn't much in the way of a good explanation for unexplored worlds. Still, Star Wars didn't have much in the way of unexplored worlds (in the movies) and they got along just fine.