A polarizer passes light that possesses a certain plane of polarization while blocking light not in that plane.
When light is reflected, it's plane of polarization tends to be parallel to the reflecting surface, so reflections can be greatly reduced with a polarizer. Aside from the uses mentioned above, it can also be used to reduce reflections from glass, such a photographing an object inside a glass case- my personal experience is that it can make a great deal of difference.
Likewise, scattered light (which is what we see in the sky) is also polarized- this polarization is proportional to cos**2(theta) where theta is the angle from the incident light. This is why a wide-angle photograph (whether from a wide-angle lens, or a stitched image) shows the banding mentioned above; we are seeing light scattered from a different angle relative to the sun. I didn't know about the mark mentioned by @saea501, but that might help with the banding. It also suggests that shooting towards, or away, from the sun with a polarizer will have minimal effects.
It is interesting (or annoying) sometimes to have polarized light (from the sky or reflected from something) impinge on something that has stress, such as a tempered car window or an airplane window while using a polarizer. You can get interesting (or annoying) patterns or colors.
These effects can't be replicated on software; polarizers are one of the few filters which can't be duplicated in software.