Introduction
This is my attempt at a skybox. I started it mostly with a desire to create a good night sky shader (of which I think I did a great job, if I may say so myself!) and then extended it with a simple day-night cycle. I am quite happy with the result, and still use it very often in my prototypes. What is special about it is that each star is procedurally generated with its own color, intensity and twinkling phase - I think it looks great in action and runs pretty well, too.
Years later, I was experimenting with low-res rendering (because of my newly found love of Ultima Underworld), and I modified the shader, as you can see below.
Night
The shader uses simple noise to divide polar space into cubes, which correspond to stars. Basically, it divides the sky sphere into discrete elements, and every pixel will then know which star it is part of. The code itself (and the idea) is pretty simple, but you can then do a lot with it. For example, you can assign a different random function to control color, size, twinkling speed, phase, and so on. The result is quite organic!
It does look much better in the actual game, though - since fragment shaders are rendered for every pixel on the screen, they adapt to whatever viewport size you're using, something that doesn't happen on a gif! Still, I hope the effect is conveyed well enough. The image on the right is a close-up and accelerated version to make the twinkling less subtle. The colors are also less vivid.
Something else I tried was to use fbm and domain warping noise to create nebulae, which you can see on the right. Once again, using 3D or 4D noise you can animate them, though these effects are probably too expensive; nebulae don't really move at observable rates, though I always like to add subtle animation for flavor (regardless of realism). I scrapped these effects, but they are possible to do with much cheaper moving textures.
Finally, you can see a fuller picture of the starry night, below. This is where shaders are great, since rendering as many stars individually wouldn't be very feasible!
Day
The day part was much simpler. The sun's position was controlled outside the shader, and a variable for "sun-height" was passed for synchronization purposes. Then, I set up a simple system of 5 colors: sun_color, day_top_color, day_bottom_color, twilight_top_color and twilight_bottom_color. When the sun is at its highest, the sky has a gradient that goes from day_top_color at the top to day_bottom_color at the bottom, and similarly for twilight, when the sun is at its lowest (but still near or above the horizon). For anything in between, I interpolate day_top_color with twilight_top_color and similarly for the bottom. This result is again interpolate with the sun's color, strongest near the sun and slowly fading.
Finally, on top of that, I also interpolate the stars as the sun nears the horizon (so you start seeing the stars before it is night, though only slightly) and quickly darken the twiling colors once the sun is below the horizon. Ignore the GIF's color-banding, which does not happen when properly rendered (as seen in the screenshots to its right).
Low Resolution
Lastly, I'll just add this section, since it wasn't as obvious as I expected. To make a low-res version of the night-sky, a simple pixelization and color-limiting shader didn't really work. This is for two reasons: (1) the stars would disappear and reappear (because most of the pixels weren't rendered) and (2) color banding looked quite ugly and unnatural.
Fortunately, the first problem was easy to solve with little change - since I had a parameter for the "grid resolution", I simply made that larger. A larger grid resolution means larger and fewer stars. In full-res, stars would appear like big circles, which isn't very natural, but it plays well with the downscaling.
The solution for the color-banding was a kind of dithering. I added some noise to the sky before applying the color-reduction shader - again, it obviously didn't look good on the full-res rendering, but it did make it a lot more natural in low-res. More "structured" dithering styles are also possible (as you see in traditional pixel art) but this looked enough for my purposes.
Source code
This was done in Unity, but since the bulk of the work was in the shader itself, you should be able to adapt it into other engines without too much trouble. The code is rather messy, but feel free to contact me if you want to experiment with it anyway.