Why does ice form on bridges even if the temperature is above freezing?

As a supplement to @tpg2114's answer, it also depends on the "wetness" of an object.

As most people should know the evaporation of water requires energy and this lowers the temperature.

The lowest temperature a wet object can reach is what is called the "wet-bulb temperature." This can be several degrees lower than the "dry-bulb temperature," the amount can vary depending on the humidity (specifically atmospheric pressure). If that wet-bulb temperature gets below 0°C, then freezing is possible.

In order for said wet object to get close to the wet-bulb temperature, some convection needs to occur in order to take that evaporated water away (i.e. wind).

This is one of the ways wind under a bridge can cause freezing under the right conditions. Another possible reason might be heat lost by radiation or the earth via conduction.

Typically freezing rain falls as water because the air is warm enough that it won't be ice, but then it freezes when it's on the surface of things because those surfaces are below freezing. This usually happens with roads and the ground when it's been a long time of very cold temperatures.

Bridges also tend to get colder, faster, than other roads because air can flow under them. They don't get the thermal insulation and thermal absorption of the ground. So regular roads may be warm enough or have warmed enough to prevent freezing while bridges have not warmed up enough yet to prevent ice from forming.

Short answer is it can't form when the temperature of the water is above the freezing point. As @Krazer and @tpg2114 have pointed out the temperature of water on surfaces will frequently be lower than the air temperature.

I'm answering just to clarify that the wet-bulb temperature is only indirectly relevant. The wet bulb temperature is not (definitionally) the lowest temperature an object can reach as a result of evaporation. It does provide a lower bound on the temperature that can be reached under outside conditions as experimentally at these pressures it turns out that the rate of convective heating of the water by the air tends to be faster than the rate of evaporative cooling of the water. Thus, the coldest evaporative cooling can reduce the water will be no lower than the coldest the water can make the air. This, of course, occurs when the air evaporates as much water as possible and the total amount of air is very large compared with the water left (so the water contains a negligible amount of thermal energy and is cooled to the air temperature) and at a temperature equal to the wet bulb temperature.

Working outside one also has to deal with radiative and convective transfers from a very very large volume of air and if still air is left around the water reservoir the rate of cooling by evaporation will drop as the air approaches saturation and the huge body of dry air will start to heat the reservoir faster than it is being cooled. Experimentally, it turns out that high wind speeds and shielded reservoirs give the largest cooling but can't actually reach the wet bulb temperature.

However, as suggested here at lower air pressures convection does not ultimate dominate evaporative cooling. In this case one can reduce the water to a lower temperature than the surrounding air and the wet bulb temperature is no longer a minimum value for the temperature evaporation can reduce surface to. Essentially this works since you are letting the highest energy molecules in the water escape and thereby reducing the average kinetic energy of the remaining molecules and the air is so thin that this effect cools the water faster than the neighboring air can heat it back up.