Exploration is an important part of the game. There's big–picture exploration (moving out further and further into the galaxy) and little picture exploration, where you get to scout out, map, and land on the surface — which I guess you could call itty–bitty picture exploration.
The starmap itself will not be random. It will be a reproduction of local space and that doesn't really change much. The Sol System will also be pretty much the same from game to game unless they start demoting a few more planets...
Inner Core systems will have some random smaller features but will have their larger attributes common to each game. Lets face it, when you make a trading game you don't put Genoa on the top of Africa or anything.
As you head out down the lines and into the Scatter, then the system details themselves will be completely random. The farther out into the Scatter you go the more alone you will be — of course sometimes you think you are the first to land somewhere only to find out that someone else had some reason to want to be really alone.
So part of it will be working to be able to get outwards into the different arms of the explored / colonized systems controlled by various Earth governments. As you move out you will find more and more unclaimed planets ( or at least, not claimed officially ), which you can scan and map. And if you happen to spot something interesting, you can land as best you can and go explore that — could be ruins, ghost towns, features of interest ( flora, fauna or mineral ), someone's unregistered landing field, etc.
Finish scouting a planet for a group — earns you deeper access to their territory. A decent deposit of minerals and a side–job delivering water to a neighboring colony allows you to upgrade your engine range and stock up on space parts. So you go further out there. You deal with more colonies, you find more unexplored planets. Maybe you choose to not report one because you want to use it as a secret storage drop. And so on and so on.
As stated elsewhere, it is not a space fighting game. It is an exploration and trading game where you can get into some fights either in your ship in the black or on your feet on the ground.
Try to picture a cross between Star Control and Mass Effect when it comes to planetary exploration. You will close survey a world with your shuttle — seeking points of interest while trying to avoid hazards if any. The map will be divided into sections where you will be able to tell at a glance if you can set down the shuttle or the Northstar. Sometimes this will be nearly on top of the point of interest, sometimes it will require a bit of a slog. Once on the surface you will be greeted with an instanced piece of terrain suitable to the world and biome which will include the point of interest, the landing point of your ship or shuttle and any menaces or unique lifeforms required.
Somewhere between a mini game and full on sub component. It will also depend greatly on how much effort the player is putting into it. Are you just exploring to further whatever missions or plot line you are working on? Or are you trying to set up your own little trade route empire by finding spots for refueling bases or trade facilities?
Though while you can set up various facilities, the player controlling dozens of starports and hundreds of facilities is not really the scope the game is aiming for. It will always be a bit more... personal.
Think Star Control–y for the survey portions. Northstar will model a plant’s surface at the mid–altitude survey level as you fly over and map. Then wherever you land it will generate character scale terrain for a zone around you based on what terrain category you had surveyed from the air. Key mission sites and facilities will be anchored in special built terrain but otherwise procedural will fill out locations around your characters. Flying over terrain will be in the abstract / sensor view, while the graphical effort goes into places where you actually land. Important sites are constant once generated — plots of terrain which you do not lay down a marker for are forgotten and landing in the same quadrant later will generate another random terrain set. Thus simulating "I was here awhile back but I can't remember exactly where we landed that time".
There will be buildings aplenty, other starships, streets, starports, offices and even the occasional military or bandit base. The Northstar world is very much about your characters doing business, chasing down clues and performing innovative jobs in all locations across known space. Along with that will go rural terrain like jungles, shorelines, deserts and a variety of airless / hostile environments. Maps with more than one floor if a building or starship also exist.
Current plans for the map is to include some of the real area within roughly 150LY of Sol, in 3D. According to Google, that's some 21,900 stars within a 150LY radius, so maybe just the spiffier ones...
Refer to Port AvSquadron for a sample exploration scenario.