This is naturally modelled as a graph structure, as you knew when you posed the question. So let's look at how we can take a graph and make it more efficient.
Let's look at topological methods. Making N^2 checks at runtime is ridiculous as you suggest, so we rule that out. Now there are two ways we can proceed - order nodes in such a way that we are likely to find locals quickly (e.g. hilbert curves which still aren't going to be effective), or pre-cache everything as the complete graph in N nodes; if N^2 is large, memory use may be prohibitive. So we may as well forego topological / classic graph style storage altogether.
Okay, so let's look at geometric methods. This is where I can see why wondra suggested octrees, however I don't think it is necessary to go that far. All you need is a single-level/depth 3D grid with reasonably cell granularity. Pre-process: If there's at least one star system anywhere in a cell, mark it occupied... assume e.g. that cells are 1 AU wide/deep/high. Now snap a sphere of the appropriate radius to this grid, roughly centring around player's position, and iterate cells within that [xyz] cubic range (that neatly surrounds your sphere) to see where you have candidates for travel.
This works well because in reality, physics tend to cause systems to cluster, so you often have systems grouped within the same cell/bucket so that you could rapidly run through only what is local. Again to return to the octree suggestion, I would only suggest implementing this if you really have a very matter-heavy galaxy. Octrees / quadtrees introduce cost due to multi-level traversal that can easily make them slower than "flat" approaches, though that is always mitigated as size grows geometrically. If you like octrees? Then by all means.
Conceptually I'd say this is simplest though and allows you to get on with other things. I guess the granularity of the grid is something you're going to have to play with - depends on your dispersion.
EDIT k-means clustering is one way you could classify various star-clusters from your starting collection of star systems; you could then create routes between them - this would allow a more traditional graph structure but with the "buckets" necessary to do fast local searches.