A basic example of this compression would be to take the current location and represent it with two parts. The first gives the location accurate to the nearest light-second, and the second gives the location within that cubic light-second.
Now, we can do huffman-coding [1] on the first part. In a gas cloud, the atoms are distributed over all possible cubes of light seconds. In a planetary system, they are concentrated in a much smaller set of planetary light seconds. This would make the huffman-coding a lot more efficient.
There are almost certainly smarter compression methods than what I just described, but the above serves as an illustration. The information-theoretic entropy of a distribution can be seen as a lower bound on the average amount of bits needed when applying compression to the distribution. I believe (am not sure) that this is a tight lower bound (i.e. there exists a compression method that gets as close to the lower limit as you want)
Why would you need more bits to describe a single atom in a galaxy vs a single atom in a gas cloud?
If a set amount of bits are required to describe an atom then that amount will not change whether or not the atom is in a galaxy or a gas cloud.