If thermodynamics says entropy always increases, how can the universe end in heat death? My understanding of entropy is that it is a measure of the available states a system can take on. In this context, if the total entropy in the universe always increases, how can it lead to a configuration where everything is at absolute zero? This has an entropy of 0, as there is only 1 possible configuration of the universe where this is the case. 
 A: 
the total entropy in the universe always increases

The total entropy of any isolated system increases until equilibrium is obtained. Then entropy stops increasing. If the system is the entire universe, then entropy will increase until the heat death.

how can it lead to a configuration where everything is at absolute zero. 

The universe being at maximum entropy does not mean the entire universe is at absolute zero.

This has an entropy of 0, as there is only 1 possible configuration of the universe where this is the case.

Not at all. Maximum entropy means there are a maximal number of configurations. 

As a useful analogy, just think of the gas in a box example. The box has a "heat death" when maximum entropy is obtained when there is a uniform gas concentration throughout the box. This doesn't put the box at absolute zero, and it doesn't put the box in a state that only is associated with a single configuration.
A: Entropy of a closed system doesn't increase without a limit. It increases until  thermal equilibrium.
It is not a zero absolute temperature point. It is the point where the whole system has the same temperature.
However, currently the Universe doesn't look to be a closed system.
Due to the expansion of the Universe, we are actually more far and far away from the heath death with time. The Universe is lesser equilibric as it was some billions of years ago. For example, the $\approx$ 300000 year old Universe, in the era of the initial (re)combination, was a nearly static, level distributed gas.
In this sense, we could say, the heath death won't happen, it already happened.
A: You may be confusing "heat death" with "energy death". Absolute zero can imply  energy death as temperature is a measure of kinetic energy. But heat is energy transfer due to temperature difference. Which is another way of saying heat is energy transfer due to thermal disequilibrium. Natural processes, ones that increase entropy, decrease thermal disequilibrium. In theory at some point temperature differences in the universe will cease at which point heat transfer is no longer possible. Thus the term "heat death". But the elimination of temperature differences is not the same thing as saying the temperature of everything in the universe will eventually be absolute zero.  Just that they will be the same, whatever that temperature is.
Temperature differences are not the only form of disequilibrium. There is also the disequilibrium associated with forces (including gravity) or pressures. These are forms of mechanical disequilibrium. Natural processes that increase entropy result in mechanical equilibrium.  If all forms of mechanical disequilibrium are eliminated, there is no longer the possibility of processes that produce mechanical work, the other form of energy transfer.
As Wikipedia puts it, the "heat death" means the universe will "evolve to a state of no thermodynamic free energy and would therefore be unable to sustain processes that increase entropy".  Entropy is maximized.
Hope this helps.
A: If the universe is expanding infinitely, and all configurations are achieved (as in the above mentioned 'asymptotic state'), then this ceases to be an 'isolated system'. The second law of thermodynamics applies specifically to isolated systems (which are not actually so easy to come by at large scale).
