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.
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)
As far as I know, thermodynamic and informational-theoretic entropy are the same except for the Boltzmann constant. It certainly seems to me that the informational entropy of the galaxy is lower than the original gas cloud.
That is, if I wanted to describe the state of a single atom in the gas cloud (lets presume the number of atoms is constant) using a perfectly tuned compression algorithm, I'd need more bits to do it than if I wanted to do the same for an atom in the current galaxy (again using a compression algorithm perfectly tuned to that situation).
Perhaps, because the gas cloud was cold, but the galaxy is 'hot' we actually need more bits because the individual particles can go faster, and thus have a larger range of possible speeds? Is this indeed enough to compensate for the much easier to describe location? Do I need to take more than just location and speed into account?