The simplest solution to storing any position is to use floating point numbers (specifically, 3 of them can store a 3D position in a
Floating point numbers have different levels of precision. Most programs and games use 32-bit single-precision floats, which are not super accurate, they work well for for most games but not ones that take place on huge scales. Single-precision floats have a limited amount of precision, which is unsuitable for games that use large scales. Single-precision floats have 23 significant binary digits (they are 32-bit, 8 of the bits are used for the exponent and 1 bit is used for positive/negative). First-person games depend on the world having better than about half a millimeter of precision. The formula
0.0005 * (2^23) shows us that errors big enough to notice appear approximately a few kilometers away from the world origin. This is fine for most games, as most games take place on scales smaller than a few kilometers.
The solution, simply put, requires us to add more significant digits. Double-precision floats are 64-bit, with 52 of those bits being significant binary digits. This is 29 more significant binary digits than single-precision floats, which increases the maximum usable area by a factor of about half a billion, to about 2 Tm (2 billion km). We go from a fifth the length of Manhattan to an area greater than the orbital radius of Saturn.
A fair question to ask is how other games handle large scales. Some games that use 64-bit doubles for large scales include Star Citizen, Arma 3, Space Engineers, and Minecraft. There's also Unigine, which is focused on being an engine for simulations, and Unigine can use doubles. For games that need somewhat large scales, sometimes maps are designed around the constraint of 32-bit floats, to be square and approximately 4 kilometers in radius, such as PlanetSide 2's Indar map. Kerbal Space Program had to implement their own 64-bit math types, doing a huge amount of calculations in user code. Even with all their effort, KSP struggled with floating-point issues for many years since the engine they are using (Unity) uses 32-bit single-precision floats, and these issues came to be known as The Kraken.
A commonly cited technique is origin shifting. This involves moving the world around the player such that the player is always near the world origin. This technique can work, but it comes with many of its own limitations. For example, it doesn't always work for multiplayer, where the server needs to have precision for all players at once. There are many tricks to make this work better, but this heavily complicates things to the point that it's both easier and more efficient to use doubles.
When this question was asked in 2015, hardware supported acceleration for 64-bit doubles was not as good as it is now, so other techniques such as origin shifting and manually calculating positions with grids and offsets (like Alan Wolfe said) were considered a better idea for AAA games that need as much performance as possible. The modern solution is to simply use doubles, since they are more precise numbers, and they are well supported on modern hardware with things like AVX2 on Intel CPUs from 2013 or newer and AMD CPUs from 2015 or newer (this is especially true if you want to make a AAA game like No Man's Sky where you want to target high-end hardware new enough to have these features).
We don't know what No Man's Sky uses, but I'm going to guess that it uses 64-bit doubles somewhere in its code, and it probably uses shifting and/or grids since it's an older game made when relying on doubles wasn't as efficient of an option.
TL;DR: If you have the choice, use doubles. They are the easiest and most reliable solution, and on modern hardware they are still a performant and efficient solution. Read more here.