Oh, i love the idea of changing the sky. I did some text searching through the game files for the term "sky". These are the results. I don't have a .nif editor or any model editing experience, so i figured i'd better leave the experimentation up to other people. Also, these results are from Civ4 1.52, but i suspect the sky definition, if there is one, didn't change much since then.
CIV4ArtDefines_Interface.xml - 44.342 bytes - Sun, 16.10.05 at 13:56 - C:\Games\Civilization 4\Assets\Xml\Art\
2.648 <Type>CIVILOPEDIA_SKY_ENVIRONMENT</Type>
2.715 <Path>Art/Interface/Screens/Civilopedia/SkyEnvironment/SkyEnvironment.nif</Path>
2.730 <Path>Art/Interface/Screens/Civilopedia/SkyEnvironment/SkyEnvironment.nif</Path>
CIV4ArtDefines_Misc.xml - 7.574 bytes - Sun, 16.10.05 at 13:56 - C:\Games\Civilization 4\Assets\Xml\Art\
1.193 <Path>Art/Terrain/Sky/Clouds01decal.dds</Path>
1.382 <Path>Art/Terrain/Sky/Clouds01.dds</Path>
2.361 <Type>ART_GLOBEVIEW_NIGHTSKY</Type>
2.417 <Path>Art/Terrain/Features/WorldCap/NightSky.nif</Path>
CIV4TerrainSchema.xml - 22.245 bytes - Sun, 16.10.05 at 13:56 - C:\Games\Civilization 4\Assets\Xml\Terrain\
14.042 <ElementType name="SkyArt" content="textOnly"/>
21.323 <element type="SkyArt"/>
CIV4TerrainSettings.xml - 1.077 bytes - Sat, 15.10.05 at 02:05 - C:\Games\Civilization 4\Assets\Xml\Terrain\
500 <SkyArt>Art/Terrain/Sky/Sky.NIF</SkyArt>