How does water extinguish fire? Heat energy from the fire is transferred to the water, isn't that how it works? How does water deprive oxygen and stop combustion? How is the specific heat of water connected to this? If we use hot water instead cold water, does that make a difference?
To sustain a fire, you need three factors: fuel, oxygen, and heat. Take away one of the three and the fire goes out. Water removes heat. Most of this "removing heat" is the evaporation - roughly 540 calories / gram, so 7x more heat than is needed to get water from 20°C to boiling (with a tip of the hat to @Jasper for pointing out erroneous value in earlier revision of answer). So using hot water is "a bit" less efficient for cooling (per unit mass of water added), but not as bad as you might think. And warm water will create (relatively) more vapor which will actually improve its role as an asphyxiant (pushing away atmospheric oxygen).
In certain kinds of fire, using water will not work well (or "at all"). That includes fires with liquid fuel - force of water can disperse the fuel into the air and thus the cooling doesn't happen where the fire happens (actually this can make things worse, since many droplets of fuel can now burst into flame away from the base), chemical fires (you might cause additional reactions, or just speed up the reaction by dissolving the components), and fires in which the fuel would react with water - for example certain kinds of metal fires (e.g. magnesium shavings, alkali metals, and the like). You also don't want to add water when there are other risks related to its use (for example high voltages present).
This is why many "general purpose" extinguishers tend to be of the "deprive of oxygen" kind - foam, powder.
Afterthought based on BeastRaban's answer: when water becomes vapor, it is lighter than air, with an atomic mass of 18 vs 29 for the usual oxygen/nitrogen mixture - but being generally cooler than a flame (most vapor will be around 100°C), it may slow down the rate with which fresh air is being drawn into the fire. As such, it is not only a coolant of the fuel (which slows down the rate of the exothermal reaction taking place), but also an asphyxiant, pushing away oxygen (or at least slowing down the rate at which it is being replenished).
To sustain fire, it is true that you need the tri-factor of oxygen,fuel, and heat.
However extinguishing fire through the use of water, is different than one would think.
Indeed, water "sucks" energy in order to change its phase, and thus reduces the heat factor, but the real crux lies in the water expansion properties.
Water is heavier than hot air, and as such sinks down into the fire. It is at the base of the fire that most of the work is done.
The water is heated up, granted, this takes up some heat, but most important of all, it turns into vapor. by the virtue of this process water expands by a factor of 300 (or maybe 3000? I can't remember that factoid from my fire-fighter days), and serves to actually create an upward moving "blanket" that separates the oxygen from the fire source.
The reasons water is to be avoided when dealing with electric fires or chemical fires are numerous: 1. In electric fires, the main concern is, that there is live wires in the vicinity, and using water might actually increase the affected area, and create additional victims/problems. 2. In chemical fires, a lot of burning agents/accelerators are lighter than water (oils for example), thus using water might actually increase the perimeter by "convecting" flammables out of containment, and into an oxygen-rich environment. 3. Some chemical agents, when burned and introduced to vapor might become airborne in forms of aerosol, while these usually do not burn as such, they can be hazardous on their own as toxins etc.
So to sum it up - the prime usage of water as a fire extinguisher is due to their ability to "inflate & separate" more than any other property they have.
There are other/ preferable methods of fire-fighting and extinguishing, that are used today, Helon gas, extinguishing foams etc. each is targeting a different (sometimes even 2) aspect of the fire-triangle.
Water does not, in general, help extinguish a fire. Typical fires, however, can be successfully attacked using water alone, as it can cool the fuel at the base of the fire or generate a vapor barrier between atmospheric oxygen and the hot fuel.
Water can accelerate liquid hydrocarbon fires by dispersing fuel.
Water can generate explosive gaseous mixtures when applied to some charcoal fires.
Water can react with some metals and chemicals to directly accelerate the fire.
Water exothermically reacts with nuclear fuel element cladding under accident conditions to generate explosive hydrogen.
Hot water versus cold would likely not matter, as the latent heat of vaporization will dominate the heat necessary to elevate cold water of a given temperature to some higher temperature (above the saturation point). In the case that oxygen removal is more important than cooling the seat of the fire, hot water might be more effective.