Why does the sky change color? Why is the sky blue during the day, red during sunrise/set and black during the night?

The keywords here are Rayleigh scattering. See also diffuse sky radiation.

But much more simply, it has to do with the way that sunlight interacts with air molecules. Blue light is scattered more than red light, so during the day when we look at parts of the sky that are away from the sun, we see more blue than red. During sunset or sunrise, most of the light from the sun comes towards the earth at a sharp angle, so now the blue light is mostly scattered away, and we see mostly red light.

Here is my older text "Mix your own reflection nebula" describing a related experiment:

"The physical process that causes the blue color of dust nebulae (like those in the Pleiades) can be demonstrated by a splendid experiment mentioned in The Feynman Lectures On Physics. You need just a beaker (or an ordinary glass) and two common chemical substances, dilute sulfuric acid ($\mathrm{H_2SO_4}$) and sodium thiosulfate ($\mathrm{Na_2S_2O_3}$) - hypo, used in photography to fix developed films. Be cautious while handling the acid – though dilute, it's still caustic. The other slight drawback of the demonstration is that this chemical reaction produces a smelly sulfur oxide, but luckily in a negligible amount.

If you mix three teaspoons of the thiosulfate into one litre of water and add a dozen drops of the acid, you get a colorless clear liquid which doesn't look very remarkable. However, after a few seconds, it gets light blue. The color first becomes brighter, then fades, and finally, the liquid gets a milky appearance, being cloudy and white (if it's yellow, either the acid or thiosulfate solution were too concentrated and the experiment should be repeated).

These changes are due to the scattering of white light on grains of sulfur which are being eliminated from the mixture and gradually grow in size. In the beginning, they are tiny and the intensity of the scattered light is inversely proportional to the fourth power of its wavelength. This means that blue light with the wavelength of 450 nm is preferred over red light, which typically has a wavelength of 650 nm, by a factor of $(\frac{650}{450})^4$, roughly 4.4. The same process, called Rayleigh scattering, is responsible for the sky blue of Earth's atmosphere. In this case, sunlight is scattered by another type of inhomogeneity, microscopic density fluctuations which arise from the chaotic thermal motion of molecules. When dimensions of the motes become comparable with the wavelength, the scattering is still selective, but not so much. Approximately, the intensity of the scattered light is now inversely proportional to the wavelength itself. This applies to dust particles in reflection nebulae and cigarette smoke. In the end, the sulfur grains are so large that they no longer favor any particular wavelength of the optical spectrum and the scattered light is white. An everyday example is water droplets in sunlit clouds.

To make the demonstration really impressive, put the beaker on an overhead projector and mask the rest with a sheet of opaque cardboard, leaving a hole in it fitting the beaker's bottom. Such an arrangement ensures ideal lighting, as it allows you to watch the light that passes through the solution to appear as a bright spot on a screen. Being increasingly impoverished of the blue constituent, which is scattered aside, it changes from white through yellow and orange to red and finally fades away, just like the sun setting in evening haze. Similar reddening (in fact de-blueing, as David Malin points out) affects the light of stars observed through interstellar dust."

I am afraid that overhead projectors, an optical device frequently used by lecturers in the 1990s when this article was written, are gone. Any idea of a substitute?

The Rayleigh scattering is one element of the solution, as j.c. explained.

However, when there is dust in the air (for instance after a volcano sends huge quantities of tiny rock particles into the sky, like what happened with Eyjafjallajökull, or because of sand or smoke particles), you might have noticed that the sunsets happen to be more colourful.

This is caused by another related light scattering effect, known as the Tyndall effect.