You can scatter points using...
uniform random coordinates (prone to uneven clusters and gaps)
or a shaken or jittered grid, where you start with a regular lattice of points, then add a small randomized offset to each (prevents big gaps/clusters, but can reveal its structure)
or a Poisson distribution (some clever algorithms to generate this can be found here)
Red Blob Games has a page that lets you play with different jittered grid vs Poisson distributions to get a sense of the trade-offs in these algorithms.
If you find your result is too uneven, you can form the Voronoi diagram of your points — generating the convex polygon that's closer to each point than any other — and move each of your points toward the centroid of its polygon. That tends to average out the spacing a little, while keeping things organic.
If you find your result is too even, you can randomly delete some points to introduce gaps, or randomly insert a few with weaker spacing criteria to create clusters.
You can also vary the spacing of your grid or Poisson samples based on an underlying density map that you generate first using noise.
Now for the connections:
To ensure that all stars are connected to the network, so you can't have an island inaccessible from the rest of the galaxy, you can use a spanning tree algorithm.
A minimum spanning tree will give you the skeleton of a constellation that touches all the stars, using the shortest links it can. Then we elaborate on that base, without violating the connectedness guarantee.
If you use Prim's algorithm (which adds links one by one), you can add a few extra links after the algorithm finishes to create cycles and alternative pathways.
If you use Kruskal's algorithm (which starts with a dense graph and removes links one by one), you can stop the algorithm early before it's weeded out more than x% of the redundant links, or give it a probability of keeping redundant links as it goes.