This old saying actually has a scientific explanation. It relates to moving high and low surface-pressure weather systems, and the way that the colors in sunlight are scattered differently by dirty and clean atmospheres. This is the explanation of how these phenomena combine to color our sunrises and sunsets.
If you look at a global map of surface pressure, you will see a string of alternating high-pressure and low-pressure areas. That is because pressure patterns are relative; i.e., if a region of lower pressure exists, it must have higher pressure on either side.
Low pressure is associated with bad weather (sailor take warning), and high pressure with good weather (sailor's delight). Low pressure causes air to converge (to try to "fill" the low), and converging air causes upward motion, which in turn produces clouds and precipitation.
In contrast, air diverges from the center of a high-pressure area. This causes downward motion, which suppresses cloud formation.
A temperature inversion (temperature increasing with height) forms at the level of the troposphere where this downward motion is strongest. This happens because downward-moving air experiences higher pressure as it descends and thus is compressed. According to the laws of physics, air heats when it is compressed. Vertical motion is inhibited at the level of the inversion; thus dirty air containing suspensions of soot, dust, and other particles (known as aerosols) is trapped near the surface.
So, atmospheric conditions in a high-pressure area are typically cloud free and dirty, and those in a low-pressure area are cloudy and relatively clean (fewer aerosols).
Light from the sun is made up of the colors in the rainbow, which correspond to different wavelengths of radiation. The blues are made up of short wavelengths and the reds of longer wavelengths. The radiative properties of a dirty atmosphere differ from those of a clean atmosphere. That is because light from the sun is scattered differently by air molecules than by aerosols (which are relatively larger). Air molecules scatter the shorter wavelengths more efficiently, and that is why the sky is blue!
Dust or aerosols scatter the longer wavelengths (red light) more efficiently, and most of that light is scattered in the forward direction (the direction in which the light is moving). Also, at sunrise and sunset the sun's rays travel through a long path of atmosphere, so these scattering processes are very efficient at those times. Therefore, sunlight traveling through a long path of dirty atmosphere at sunrise or sunset is made up of primarily the reddish wavelengths when it reaches the observer (e.g., look at the color of smog in Los Angeles or Denver). A cleaner atmosphere at sunrise or sunset is colored by a mixture of all but the blue colors, giving it a yellowish appearance.
Now you have the science behind the adage. Picture yourself on a ship in the middle of a mid-latitude ocean. There the wind (and thus storm paths) is from west to east. It is morning and you are watching the sunrise. It is red. Since it is morning you are looking east, and the red sky indicates that there is high pressure there. Because you are in the mid-latitudes, the high is moving eastward--away from you. That could only mean that a low, and very likely an associated storm, is moving toward you from the west. Sailor take warning! Now picture yourself watching the sunset from the ship, and the western sky is red. That means that an area of high pressure is to your west, the westerlies are moving it toward you, and good weather is on the way--sailor's delight!
Note that this only works in the belt of westerlies, from about 30 degrees to 60 degrees latitude in both the northern and southern hemispheres. The region 30 degrees on either side of the equator is characterized by easterlies (the trade winds). This adage would be opposite in that region.