While water heating is typically only 10-20% of a home's total energy budget, the exact amount varies widely due to differences in how energy efficient the house is in all the other respects and how much hot water the household uses.  An house that isn't very energy efficient, but doesn't use a lot of hot water will see little gain from improving the hot water efficiency, while a very efficient house that uses quite a bit of hot water (for example, due to a high level of occupancy), can see sizable gains. 

The easiest thing to do is to make sure you have an efficient hot water heater.  Electric heaters are nearly 100% efficient, and potentially carbon neutral (more about this here), but since the US average is that 70% of the electric is generated by burning fossil fuel, a process that is typically only 33% efficient, the actual efficiency of an electric hot water tank (based on fossil fuel consumed) is more like 53%.  While both natural gas and fuel oil are not renewable resources, it is more efficient to burn them directly in your own hot water heater than to have the electric company burn them.  A typical new gas hot water heater will be of the "mid efficiency" type--somewhere around 82% efficient.  The next step up, a "high efficiency" or "condensing" unit, will be more like 94% efficient.  Buy a unit with a piezoelectric starter rather than a pilot light, as pilot lights consume a significant amount of energy. 

In heating dominated climates (ie the northern US), it is best to put the hot water tank somewhere within the heated space so that the heat loss from the tank goes into the house.  When installed inside the house, select a direct vent model that brings in outside air for combustion and puts it exhaust outside in order to avoid indoor air quality problems.  In cooling climates the opposite is true--keeping the tank out of the heated space avoids having the air conditioner having to remove its standby heat.

Note: As a practical matter, electric hot water tanks heat water much slower than gas units--typically 3-5 times slower.  As long as the house uses hot water efficiently and the tank is big enough, this isn't a problem.

The next easiest thing to do is to convert to a tankless or on-demand unit.  In general these are drop in replacements for standard tank heaters, even when they are, they don't quite operate the same.  Unlike tank heaters, on demand units have a small delay to create hot water, so you end up waiting a bit longer for hot water to come. Additionally, there is a minimum flow rate for the unit to turn on--typically 1/2 to 3/4 a gallon per minute.  If you turn the sink on at a low flow rate, the water will never get hot because the unit will not turn on.

The most common limitation is that tankless units draw gas at 3-4 times the rate of a standard gas hot water heater because they must heat the water instantly, and as a result a gas supply line that was adequate for a tank heater may be too small for a tankless unit.  Note that tank heaters deliver hot water from the top of the tank, where it is already heated and heat the cold water coming into the bottom.  This allows them to heat the water much slower than a tankless unit.  This works because hot water is a fluid that is lighter than cold water, and hence hot water will rise.

Almost all the tankless units sold use natural gas or propane as fuel, because electric has a much lower energy density.  The typical use of electric tankless units is for a low volume point-of-use, such as a bathroom sink.  A few manufacturers do make whole house electric on demand units, but because these units draw around 20kw (nearly 100 amps at 240 volts) few houses can accommodate one within the constraints of a standard 200 amp service panel (other than a house small enough that it could use a 100 amp panel).   For anyone trying to reduce their reliance on fossil fuels (aren't we all?), the fact that most tankless units are gas fired creates this dilemma between trying to use less energy and using less fossil fuel energy.

How much energy you'll save by going with a tankless unit will vary based on many factors.  Since most tanks are poorly insulated (and even the bests one are only like R10), the only fair comparison is when a blanket is also installed (R10 fiberglass, a $20 item).  Then you must consider whether the tank is inside the house or out and what your climate is.  If the tank is inside the heated space, and you live in a heating climate (like Seattle), then 8-9 months of the year, the waste heat isn't wasted--its heating your house.  If you live in a cooling climate (Florida), most people just move the heater outside.  If you're somewhere in between (say Ohio), then stopping this heat loss is a bigger deal.

It should go without saying that the more hot water you use, the less standby loss affects your total energy use.  If your heater uses a pilot light (considered desirable for people who's power goes out often) that use is likely to be much greater than any standby loss.  For comparison sake here are some numbers:

As you can see how much savings you get varies from 70% of the total if your comparing low use/no pilot/solar pre-heat with a typical R6 tank set at 140 and kept in a 50F basement ...or could be as little as 5% if your comparing a high use/pilot light with a quality tank covered in a R10 blanket kept in a 70 room. Due to this variation and the other complication factors like climate, I find the tankless industry's savings claims to be generally inflated.

On-demand units do not deal with solar pre-heated water very well.  Most units specifically state they are not compatible with pre-heated water, and the ones that say they are will all produce water that is too hot when given water that is just slightly too cool (eg 110F in results in 140F or more out, not 120F).   The problem is that the minimum burn rate is around 20k BTU/hr, or about 333BTU/min.  When you consider a flow rate of 3/4gallon/minute (the typical minimum), that 333BTU/min will result in the water rising 50F (ie 333BTU/6lbs water = 50F).  At 1.5gpm, you'd get only half the rise in temperature.   There is little acknowledgement out there that you need a tempering valve and no consensus on where to put the valve.  At issue is the fact that tempering valves lower the temperature of the hot water by at least 20F even when they don't need to (this is apparently because they never quite shut the cold side off).

The only solution that appears to me to work is to set the tankless unit to 20F higher than you want (so 140 instead of 120), and install a tempering valve on the output of the tankless unit.  If you set the tankless unit to 120 the water coming out of the tempering valve will be 100 even if the tempering valve is set to 140. (note: I've been told that the Watts 70a might only lower the temp by 10F).  The downside of this solution is that it increases the minimum flow rate to turn on the tankless unit (since some of the water at the faucet is always coming from the cold side of the tempering valve).

In order to get around these problems, I came up with a small tank solution (see below) that gets around the problem with a small tank hooked up to a tankless unit, but it does introduce some standby loss.

Those dedicated to energy efficiency will want a solar hot water collector.  These units are not cheap (typically a few thousand dollars), but make a much bigger impact than any other strategy.  In sunny climates, a solar collector will supply nearly all the hot water you need.  In dark, rainy climates like Seattle, solar hot water will supply most of your hot water for about six months a year, and give you at least a little heat the rest of the year.

In the typical configuration, the solar collector heats a separate pre-heat tank, and then water from the pre-heat tank is fed into a standard hot water tank which adds whatever amount of heat is necessary to bring the pre-heated water up to the set-point temperature (typically 120F).  The disadvantage of this system is that there are now two tanks leaking heat, not just one. A more efficient system is to use a tankless unit: see the tankless section for the complication of doing that.

Alternative approaches

The heat pump is a potential solution to the low energy value of electric.  Depending on the temperature of the heat sink for the pump, a heat pump will deliver 2-4 times as much heat as is in the energy to run the pump.  Air source heat pumps use ambient air as the sink, and although they are efficient when the air temperature is above about 45, they're efficiency goes down dramatically as the air temperature goes down toward freezing and at some point stop working altogether (note: newer, two stage heat pumps apparently work down to 0F).  Ground source heat pumps use the ground or a pond as their heat sink because by going down a few feet, those areas are nearly a constant temperature all year and usually much warmer than winter air.

A number of manufactures make air source water heaters (all tank units), but they are not readily available.  As with electric, it is difficult for a heat pump to deliver the instantaneous quantity of heat required for a tankless unit.  While a heat pump water heater can heat much faster than a standard electric resistance heater, it is still slower than gas tank unit. The typical rate appears to be around 15 gallons/hour, while a gas tank unit could be 50 or more, and a tankless unit will be over 100.

Because air source heat pump water heaters eject cold air during operation, it is probably best to send the cold air outside, although this will pull in outside air, which may be as cold as the exhaust air.  Since they don't work in cold air, there is no choice but keeping them in heated space--in effect they are using indoor heated air to heat water.

There are no ground source hot water units that I'm aware of, but it is likely someone makes a ground source heat pump that supplies both heat and hot water.  Ground source heat pumps can be very expensive because they typically require a digging long trenches or drilling many holes so as to use a large area of earth as the heat sink (heat moves quite slowly in soil).

In cooling climates, specially designed air conditioners can supply hot water for free as a side effect of their operation.  This is because air conditioners are just heat pumps--the move heat from inside to out, so it is nearly as easy to heat water instead of dumping the waste heat outside. 

A Small storage tank and tankless heaters combine the best of both technologies.  Storage tanks deliver heat with no delay and don't have a minimum flow rate, while tankless units reduce standby loss.  By using a small tank (5 gallons or so) and super insulating it, the standby loss is nearly as low as a tankless unit by itself.  The tankless unit then heats the water in the small tank indirectly (via a circulation pump) making it seem that the tank is actually much larger than it is.  This configuration is also likely to eliminate the problem of tankless units overheating solar pre-heated water because the overheated water is now mixed with the existing water in the small tank, thereby limiting the output temperature (note: this is just a theory, I know no one who has tried this).  Since circulation pumps draw about 50w, even if it ran for 1 hr a day, the total energy use is 171 BTU, with another 500 BTU standby loss.

This isn't as good as finding a gizmo that tempered the output water without always dropping the temperature 20F.

Combined heat-H/W.  These systems offer a small efficiency in that they attempt to use the burner more efficiently.  In hydronic heating systems, one hot water tank often  supplies both heat and hot water.

Final thoughts

The appeal of on-demand (tankless) units is great because they have no standby losses, and the idea of using a small, very well insulated storage tank may well alleviate their limitations.  It seems likely that neither electric nor heat pumps are likely to power any whole house on-demand unit.  This makes the only reasonable carbon neutral choice to be some kind of biogas--although I haven't looked into how practical this is, if it was, its a very appealing solution. 

Resources

The US DOE, energy efficiency and renewable energy website guide to water heaters at: http://www.eere.energy.gov/consumer/your_home/water_heating/index.cfm/mytopic=12760 

American council on energy efficiency guide to hot water heaters at: http://www.aceee.org/consumerguide/topwater.htm

Another take on the topic from Home Energy magazine:
http://homeenergy.org/archive/hem.dis.anl.gov/eehem/96/960510.html