making skies are the best part about the terrains. They can make or break the overall atmosphere of your terrain.
The first step is to have a theme for your terrain. Say you have a Barrens terrain, with desert life. Your best bet is to take a sky color such as brown or orange to match the overall color scheme. If you get good and get extra creative, you can pan into opposite color themes, and abstract color schemes.
The next step is to have the right models. The UTM (Ultimate Terrain Map) is the best place to start, since they give you custom model clouds and Glows.
Also with making skys, experiment alot with them, and use numerous techniques like making stars in the sky (a bunch of tiny glow/star models and CTRL+UP them) or change the color of a cloud model to red, while you have the fog set to blue(just an example) and you can get great results.