They do freeze. They just don't normally freeze solid.
In the more extreme climates, like North Dakota, engineers incorporate heating systems into the tank design. Specifically, the central pipe that runs from ground level up into the bottom of the tank is called a riser. Water is pumped into the base of the riser and allowed to rise into the tank. Many tank risers are wrapped with heat tape, covered with insulation and capped by an aluminum jacket. In addition, a heating system may be installed in an adjacent building or into the valve pit underneath the riser. The heater introduces heated water or steam into the base of the riser. In either case, the heat rises into the tank to retard freezing.
Ice forms on the surface of the contents, in many cases several feet thick. Normally, this ice layer floats on the surface as the water level rises and falls. Many times the ice freezes to the roof or upper walls of the tank and remains there as the level fluctuates underneath under daily usage.
In more temperate climates, steel ladders are installed inside the tank, and riser and water level control probes hang from the roof. In colder climates, all inside fixtures must be left out since the ice layer tends to rip them out.