If you are using Ubuntu (or Kubuntu, or Xubuntu, etc.) Intrepid, you will find that Celestia as installed from the Add/Remove option is missing a lot of textures. This is because the Ubuntu package maintainers apparently had a problem with the licensing of several textures and thus put them into the package celestia-common-nonfree. However the Celestia installation has been set up so that the celestia package does not depend on celestia-common-nonfree, which has to be selected separately.
The whole thing seems ridiculous -- why would the average user want a partial installation? Silently supplying users with incomplete applications in the name of license purity is not going to win anyone any friends. This issue has already come up in the Celestia forums -- doing this is basically going to cause the Celestia community to get a whole load more bug reports from Ubuntu users, when in fact the fault is with the package maintainers at Ubuntu.
A far better solution would have been to put the entire application into the nonfree repository. The current solution will only satisfy those with a rabid fetish for ultra-free software, and I doubt such people are going to be using Ubuntu in the first place.