Basically the polarizing filters remove a part of light reflected by surfaces such as
- water droplets forming haze (as in Nick's example #1),
- glass (as in Nick's example #2),
- (see|river|pool) water surface
The magnitude of that effect depends on the angle between the filter axis (you can rotate it) and the axis perpendicular to the reflecting surface.
However, the orientation of the part of droplets surface reflecting the sun towards you is not oriented the same way for droplets that are towards the sun and for droplets 90° from it. So your filter will be most efficient in one direction and not at all in an other.
Therefore it will be more or less efficient at "removing" haze, depending on where you aim; that makes sometimes strange effects on wide-angle landscape shots.
Also take care that polarizing filters change color balance to some extent. That's not a big deal most of the time.
Now for your original question : it totally depends on the kind of pictures you intend to take. It's quite a must-have for landscape photography, or if you're shooting through glass surfaces (windows), but it adds little to many other cases.