What exactly is heat?
I'll try to give an answer in purely classical thermodynamics.
Summary
Heat is a way of accounting for energy transfer between thermodynamic systems. Whatever energy is not transferred as work is transferred as heat. If you observe a thermodynamic process and calculate that system A lost $Q$ calories of heat, this means that if the environment around system A were replaced with $Q$ grams of water at $14\sideset{^{\circ}}{}{\mathrm{C}}$ and the process were repeated, the temperature of that water would rise to $15\sideset{^{\circ}}{}{\mathrm{C}}$.
Energy
Energy is a number associated with the state of a system. It can be calculated if you give the state variables - things like mass, temperature, chemical composition, pressure, and volume. (These state variables are not all independent, so you only need to give some combination of them.)
Sometimes the energy can be accounted very simply. For an ideal gas, the energy is simply proportional to the temperature, number of molecules, and number of dimensions. For a system with interesting chemistry, internal stresses and deformation, gravitational potential, etc. the energy may be more complicated. Essentially, we get to invent the formulas for energy that are most useful to us.
There's a nice overview of energy, summarizing Richard Feynman, here. For a more theoretical point of view on where these energy formulas come free, see Lubos Motl's answer here.
Energy Conservation
As long as we make the right definitions of energy, it turns out that energy is conserved.
Suppose we have an isolated system. If it is not in equilibrium, its state may change. Energy conservation means that at the end of the change, the new state will have the same energy. (For this reason, energy is often treated as a constraint. For example, an isolated system will maximize its entropy subject to the constraint that energy is conserved.)
This leaves the question of what an isolated system is. If we take another system (the environment) and keep it around the isolated system, we find no observable changes in the environment as the state of the isolated system changes. For example, changes in an isolated system cannot change the temperature, pressure, or volume of the environment. Practically, an isolated system should have no physical mechanisms for interacting with the rest of the universe. Matter and radiation cannot leave or enter, and there can be no heat conduction (I'm jumping the gun on that last one, of course, but take "heat conduction" as a rough term for now). A perfectly isolated system is an idealization only.
Next we observe systems A and B interacting. Before the interaction, A has 100 joules of energy. After interacting, A has 90 joules of energy, so it has lost 10 joules. Energy conservation says that if we measure the energy in system B before and after the interaction, we will always find that system B has gained 10 joules of energy. In general, system B will always gain exactly however much system A loses, so the total amount is constant.
There are nuances and caveats to energy conservation. See this question, for example.
Work
Work is defined by
$$\textrm{d}W = P\textrm{d}V$$
$P$ is pressure; $V$ is volume, and it is fairly easy to give operational definitions of both.
Using this equation, we must ensure that $P$ is the pressure the environment exerts on the system. For example, if we took a balloon into outer space, it would begin expanding. However, it would do no work because the pressure on the balloon is zero. However, if the balloon expands on Earth, it does work given by the product of its volume change and the atmospheric pressure.
That example treats the entire balloon as the system. Instead, we might think of only the air inside the balloon as a system. Its environment is the rubber of the balloon. Then, as the balloon expands in outer space, the air inside does work against the pressure from the elastic balloon.
I wrote more about work in this answer.
Adiabatic Processes
Work and energy, as described so far, are independent ideas. It turns out that in certain circumstances, they are intimately related.
For some systems, we find that the decrease in energy of the system is exactly the same as the work it does. For example, if we took that balloon in space and watched it expand, the air in the balloon would wind up losing energy as it expanded. We'd know because we measure the temperature, pressure, and volume of the air before and after the expansion and calculate the energy change from a formula.
Meanwhile, the air would have done work on the balloon. We can calculate this work by measuring the pressure the balloon exerts on the air and multiplying by the volume change (or integrating if the pressure isn't constant).
Remarkably, we could find that these two numbers, the work and the energy change, always turned out to be exactly the same except for a minus sign. Such a process is called adiabatic.
In reality, adiabatic processes are approximations. They work best with systems that are almost isolated, but have a limited way of interacting with the environment, or else occur too quickly for interactions beside pressure-volume ones to be important.
In our balloon, the expansion might fail to be adiabatic due to radiation or conduction between the balloon and the air. If the balloon were a perfect insulator and perfectly white, we'd expect the process to be adiabatic.
Sound waves propagate essentially adiabatically, not because there are no mechanisms for one little mass of air to interact with nearby ones, but because those mechanisms (diffusion, convection, etc.) are too slow to operate on the time scale of the period of a sound wave (about a thousandth of a second).
This leads us to thinking of work in a new way. In adiabatic processes, work is the exchange of energy from one system to another. Work is still calculated from $P\textrm{d}V$, but once we calculate the work, we know the energy change.
Heat
Real processes are not adiabatic. Some are close, but others are not close at all. For example, if I put a pot of water on the stove and turn on the burner, the water's volume hardly changes at all, so the work done as the water heats is nearly zero, and what work is done by the water is positive, meaning the water should lose energy.
The water actually gains a great deal of energy, though, which we can discover by observing the temperature change and using a formula for energy that involves temperature. Energy got into the pot, but not by work.
This means that work is not a sufficient concept for describing energy transfer. We invent a new, blanket term for energy transfer that is not done by work. That term is "heat".
Heat is simply any energy transferred between two systems by means aside from work. The energy entering the boiling pot is entering by heat. This leads to the thermodynamic equation
$$\textrm{d}E = -\textrm{d}W + \textrm{d}Q$$
$E$ is energy, $W$ work, and $Q$ heat. The minus sign is a convention. It says the if a system does work, it loses energy, but if it receives heat, it gains energy.
Interpreting Heat
I used to be very confused about heat because it felt like something of a deus ex machina to say, "all the leftover energy must be heat". What does it mean to say something has "lost 30 calories through heat"? How can you look at it and tell? Pressure, temperature, volume are all defined in terms of very definite, concrete things, and work is defined in terms of pressure and volume. Heat seems too abstract by comparison.
One way to get a handle on heat, as well as review everything so far, is to look at the experiments of James Joule. Joule put a paddle wheel in a tub of water, connected the wheel to a weight so that the weight would drive the wheel around, and let the weight fall. Here's the Wikipedia picture of the set up:
$\hspace{100px}$
.
As the weight fell, it did work on the water; at any given moment, there was some pressure on the paddles, and they were sweeping out a volume proportional to their area and speed. Joule assumed that all the energy transferred to the water was transferred by work.
The weights lost energy as they fell because their gravitational potential energy went down. Assuming energy is conserved, Joule could then find how much energy went into the water. He also measured the temperature of the water. This allowed him to find how the energy of water changes as its temperature changes.
Next suppose Joule starting heating the water with a fire. This time the energy is transferred as heat, but if he raises the temperature of the water over exactly the same range as in the work experiment, then the heat transfer in this trial must be the same as the work done in the previous one. So we now have an idea of what heat does in terms of work. Joule found that it takes 4.2 joules of work to raise the temperature of one gram of water from $14\sideset{^{\circ}}{}{\mathrm{C}}$ to $15\sideset{^{\circ}}{}{\mathrm{C}}$. If you have more water than that, it takes more work proportionally. 4.2 joules is called one calorie.
At last we can give a physical interpretation to heat. Think of some generic thermodynamic process. Imagine it happening in a piston so that we can easily track the pressure and volume. We measure the energy change and the work during the process. Then we attribute any missing energy transfer to heat, and say "the system gave up 1000 joules (or 239 calories) of heat". This means that if we took the piston and surrounded it with 239 grams of water at $14\sideset{^{\circ}}{}{\mathrm{C}}$, then did exactly the same process, the water temperature would rise to $15\sideset{^{\circ}}{}{\mathrm{C}}$.
Misconceptions
What I discussed in this post is the first law of thermodynamics - energy conservation. Students frequently get confused about what heat is because they mix up its definition with the role it plays in the second law of thermodynamics, which I didn't discuss here. This section is intended to point out that some commonly-said things about heat are either loose use of language (which is okay as long as everyone understands what's being said), or correct use of heat, but not directly a discussion of what heat is.
Things do not have a certain amount of heat sitting inside them. Imagine a house with a front door and a back door. People can come and go through either door. If you're watching the house, you might say "the house lost 3 back-door people today". Of course, the people in the house are just people. The door only describes how they left. Similarly, energy is just energy. "Work" and "heat" describe what mechanism it used to leave or enter the system. (Note that energy itself is not a thing like people, only a number calculated from the state, so the analogy only stretches so far.)
We frequently say that energy is "lost to heat". For example, if you hit the brakes on your car, all the kinetic energy seems to disappear. We notice that the brake pads, the rubber in the tires, and the road all get a little hotter, and we say "the kinetic energy of the car was turned into heat." This is imprecise. It's a colloquialism for saying, "the kinetic energy of the car was transferred as heat into the brake pads, rubber, and road, where it now exists as thermal energy."
Heat is not the same as temperature. Temperature is what you measure with a thermometer. When heat is transferred into a system, its temperature will increase, but its temperature can also increase because you do work on it.
The relationship between heat and temperature involves a new state variable, entropy, and is described by the second law of thermodynamics. Statements such as "heat flows spontaneously from hot bodies to cold bodies" are describing this second law of thermodynamics, and are really statements about how to use heat along with certain state variables to decide whether or not a given process is spontaneous; they aren't directly statements about what heat is.
Heat is not "low quality energy" because it is not energy. Such statements are, again, discussion of the second law of thermodynamics.
Reference
This post is based on what I remember from the first couple of chapters in Enrico Fermi's Thermodynamics.
The word "heat" is used to apply to energy transfer from a high-temperature body to a low-temperature body. You should never say that a body contains a certain amount of heat; you should only say that a certain amount of heat flowed from one body to another. As Nic correctly says, it comes in units of energy (joules, or sometimes calories).
Three meanings:
amount of energy (in joules) transfered from a "hot body" to "cold body"
the process of 1.
a non exact 1-form Q such that $dE=W+Q$ or $Q=TdS$
Heat is not a substance. Heat cannot be "extracted" from a body. Microscopically heat is "the flow of kinetic energy" during the process of achieving thermal equilibrium.