Given the law of conservation of energy, it is often evocative and helpful to imagine energy as a kind of permanent "stuff" and along with this an imagination of "where" it is.
But this doesn't always work, so another "answer", complementary to the others, is the following.
What is it "truly"? It is simply a manifestation of a system's time shift invariance. It is a manifestation of a system's symmetry.
A modern insight into the "reason" for conservation of energy in a system is Noether's theorem. If a system's Lagrangian has a continuous symmetry, then, by Noether's theorem, there is one conserved quantity for each such symmetry. Most physical systems "don't care" where we put our $t=0$ origin for our co-ordinate system. The $t=0$ origin's exact location is an artifact of our description of a physical system, not of the system itself. Therefore, for most systems, if we impart the time shift $t\to t+\alpha$ for any $\alpha\in\mathbb{R}$, then our equations describing the system's physics do not change.
The conserved quantity that arises from a system's time shift invariance symmetry by Noether's theorem is what physicists call energy.
So when some moving objects in a system slow down and you want to know "where" their kinetic energy has gone to, you can instead say that properties of those and other objects have changed so as to uphold the total system's invariance to time origin shift. Or, there must be a corresponding "balancing" change by dent of a certain symmetry. The question of "where" then doesn't arise.
This is a fairly abstract thinking, but you you might find it helpful in some situations - I urge you to think of it as complementing rather than replacing more elementary intuitive notions of energy as a "stuff".
As user Christoph says (thanks Christoph):
note that we need to answer the 'where' question for anything besides gravitational energy if we want to apply general relativity...
This is very true and it also serves to illustrate the limitations of the Noether symmetry idea, at least as far as energy is concerned. What Christoph means is that in General Relativity, one must indeed "locate" energy by writing down the so called stress energy tensor $T$ to be the source term in the Einstein field equation. The $0 0$ component of $T$ is the energy density in space per unit volume as a function of position and time (i.e. a manifest assertion of "where the energy is").
In General Relativity, however, my answer does not apply, because there is in general no time shift invariance symmetry anymore. Global energy need not be conserved in general relativitstic systems - although there is still a local conservation of energy, meaning roughly that energy conservation approximately holds for systems that are small enough in both their spatial and temporal extent.
