How to render infinite universe?

There's a number of pieces to this puzzle, each of which will provide a deep and interesting rabbit hole of exploration. Some of them are:

• Level of Detail -- automatically (or "manually") choosing detailed or simplified models, or even sprites or just dots, or for objects as they are further away.
• Culling -- choosing to only draw what's needed. This might be what's in the field of view (frustum culling), what's not hidden behind other things (occlusion culling), or other ad hoc methods. (@Alan Wolfe's answer describes some of the ways to organize your data that help facilitate culling.)
• Streaming -- pulling world-data from storage into memory as needed, if it doesn't all fit in memory at once
• Sky box -- very distant objects can be pre rendered onto a sphere that is at "infinite distance" from the camera.

And your own secret sauce will be what combination of these, and other, techniques you use, and when, based on your particular application needs.

This is based on my speculation and skimming through Celestia's source code.

Celestia allows you to fly around a planet and zoom out to see the whole galaxy. I browsed its source code and found it used an octree, a structure to recursively divide space into 8 octants.

The renderer would render the environment by traversing the octree, and don't traverse far objects deeply.

Celestia also keep track of absolute magnitude of an octant, where the absolute magnitude of an octant is based on the absolute magnitude of the stars inside the octant. If the octant is close together, Celestia renders the stars individually, and if the octant is far away Celestia renders the octant as one star of the octant's magnitude.

Also, there can be meaningful hierarchy attached to objects. For example, if you are close (radius declared in database) to a star, its planets are rendered. If a planet is close enough (a cutoff of pixels on screen), its 3D model is drawn.

Other space games I can name of are Orbiter and Kerbal Space Program, which are closed-source. I also looked into Frontier Galaxy, which has procedurally generated star map. There is a website analyzing how the game works by its disassembly: http://www.jongware.com/galaxy1.html

Anything that is either hierarchical and/or sparse should help you out here. There's a lot of empty space, so not having to use storage to represent empty space is a must. A typical hierarchical approach would be something like an Oct tree which recursively subdivides space into 8 smaller cubes, and you can store objects in the smallest cube that they can completely occupy. An octree is also pretty good for you being able to query it for a list of all objects in a view frustum which will let you get a list of only the objects that are within your viewing angle and aren't too distant. A sparse solution could be something like a sparse grid where you can ask for information about any x,y,z location, but you only have to store information for cells that aren't empty space. Other common hierarchical approaches used include bsp trees (they split space into 2 half spaces recursively) as well as k-d trees which do similar. I personally think an octree could be a good start for you, making sure to subdivide only as deeply as needed so you don't waste memory on empty space. also, you might end up wanting a different solution for your static objects versus your dynamic objects. Some solutions (like bsp) can be very efficient, but take a long time to construct so aren't usually a good choice for moving / changing objects. Hope that helps, let me know if you have any questions about the details!