Typical approaches are skyboxes or skydomes. Both techniques involve creating some simple geometry that is always rendered in a fixed position relative to the view, and applying a texture to it. The quality of the resulting effect can depend heavily on the quality of the texture artwork, so if you don't have great art skills you may want to opt for something else. Tools like Terragen can help produce decent art though, and this question has a set of links to other tools of a similar nature.
A less obviously art-dependent approach is to do the whole thing procedurally. You can create a vertex-color based skydome (links and information here) which will allow you to adjust the colors according to some empirical (or other) models for sky coloring -- Preetham and Shirley's model is particular nice, if I recall correctly.
You can then apply procedural starfield generation which you render near the sky dome (perhaps as a fixed particle system, or via texture splatting, or whatever).