I'm happy to accept and use conservation of energy when I'm solving problems at Uni, but I'm curious about it to. For all of my adult life, and most of my childhood I've been told this law must hold true, but not what it is based on.
On what basis do we trust Conservation of Energy?
Let me expand a bit on Manishearth's answer. There's an idea going back a long time called the principle of stationary action. See http://en.wikipedia.org/wiki/Principle_of_stationary_action for a description that isn't too mathematical. In the 18th and 19th centuries century the mathematicians Lagrange and Hamilton found ways of using this to describe mechanics. Then in the early 20th century the mathematician Emmy Noether discovered that in Lagrangian mechanics if a symmetry of the equations existed this meant there was a corresponding conservation law. As Manishearth says, one example of this is that time symmetry means that energy must be conserved.
Strictly speaking, the symmetry involved is "shift symmetry of time". This means that if I do an experiment, the time I do it doesn't matter so I'd get the same result tomorrow as I do today. If this is true Noether's theorem means that energy must be conserved.
Experimentally we find that repeating experiments does indeed give the same results, and we also find that everything observed so far obeys Lagrangian mechanics. This suggests that energy is indeed conserved. Strictly speaking this is an experimental observation not a proof, but few doubt that the principle applies as the universe would be a strange place if it didn't.
Wikipedia has lots of articles on Langrangian Mechanics and Noether's theorem, but they're a bit intimidating for the non-mathematician. If you're interested in knowing more Googling should find you plenty of more accessible articles.
Historically, energy conservation was enforced by postulating new physics each time an apparent violation was discovered. This makes energy conservation not so much an empirical observation - rather it is an organizing principle that we impose successfully to explain how Nature behaves. This it is made true by definition!
Indeed, most real processes are dissipative, i.e., they actually lose energy. It is one of the great accomplishment of 19th century physics that in spite of this, energy conservation was postulated and used successfully to build a coherent theory of thermodynamics, which ultimately lead to a great unification of physics. (The last bit of this, the unification of gravity and quantum mechanics, is still a hard research problem.)
Observed dissipation doesn't contradict energy conservation, as the lost energy is, on a fundamental level, still there - it just moved from the part of a system described by our methods to unmodelled parts (the ''environment'') that picks up this energy. This is why real processes usually move to a state of least free energy (where the free part of the energy depends on how a system is embedded into the environment).
Conservation of energy is a property that a particular physical system may have. Most often, one determines if a system conserves energy by studying the symmetries of the Lagrangian. As others have said, conservation of energy is associated with the Lagrangian being symmetric in time.
But there is no a priori reason that all possible Lagrangians conserve energy. For example, consider the Lagrangian of the universe. The universe, as we now know, is expanding, meaning it is certainly changing as a function of time. Thus, on a very global scale, the energy of the universe isn't conserved. But this applies to only the very largest of scales. Locally, we don't notice the expansion of the universe, and energy is conserved to excellent precision.
But, taking a step back, saying that conservation of energy can be derived from a symmetry of the Lagrangian is a bit of a circular argument. If you write down a Lagrangian that is invariant under time symmetry, then you can define an energy that doesn't change in time. That's true.
But I guess none of this yet answers your question, which was "On what basis do we trust conservation of energy." The answer to that is the vast experimental evidence, from day-to-day experiences to precision physical measurements. Based on experiment, our local laws of physics don't change as a function of time.
It seems to me the obvious answer is that it agrees with all the experiments.
I am an experimentalist after all, (the neutrino is perhaps the best "missing energy" story.)
For about two centuries, many people had tried to devise 'perpetual motion engines', but they had failed. To explain this failure, theoretical thermodynamics physicists and engineers arrived at the First Law of Thermodynamics, which is essentially the Law of Conservation of Energy. Some physicists then explained this Law as a byproduct of Newton's Laws of Motion.
In 1905, Einstein's Mass-Energy Equivalence Principle predicted that mass and energy are convertible. This implied that the Law of Conservation of Energy is valid only if there is no change in mass.
