I had a left over coffee cup this morning, and I tried to wash it out. I realized I always instinctively use hot water to clean things, as it seems to work better.  

A Google search showed that other people get similar results, but this Yahoo answer is a bit confusing in terms of hot water "exciting" dirt.    

What is the physical interaction between hot water and oil or a material burnt onto another vs  cold water interaction?

The other answers are correct, but I think that you might benefit from a more "microscopic" view of what is happening here.
Whenever one substance (a solute) dissolves in another (a solvent), what happens on the molecular scale is that the solute molecules are surrounded by the solvent molecules.
What causes that to happen? As @Chris described, there are two principles at work - thermodynamics, and kinetics.
In plain terms, you could think of thermodynamics as an answer to the question "how much will dissolve if I wait for an infinite amount of time," whereas kinetics answers the question "how long do I have to wait before X amount dissolves." Both questions are not usually easy to answer on the macroscopic scale (our world), but they are both governed by two very easy to understand principles on the microscopic scale (the world of molecules): potential and kinetic energy.
Potential Energy
On the macroscopic scale, we typically only think about gravitational potential energy - the field responsible for the force of gravity. We are used to thinking about objects that are high above the earth's surface falling towards the earth when given the opportunity. If I show you a picture of a rock sitting on the surface of the earth:

And then ask "Where is the rock going to go?" you have a pretty good idea: it's going to go to the lowest point (we are including friction here).
On the microscopic scale, gravitational fields are extremely weak, but in their place we have electrostatic potential energy fields. These are similar in the sense that things try to move to get from high potential energy to lower potential energies, but with one key difference: you can have negative and positive charges, and when charges have the opposite sign they attract each other, and when they have the same sign, they repel each other.
Now, the details of how each individual molecule gets to have a particular charge are fairly complicated, but we can get away with understanding just one thing:
All molecules have some attractive potential energy between them, but the magnitude of that potential energy varies by a lot. For example, the force between the hydrogen atom on one water molecule ($H_2O$) and the oxygen atom on another water molecule is roughly 100 times stronger than the force between two oxygen molecules ($O_2$). This is because the charge difference on water molecules is much greater (about 100 times) than the charge difference on oxygen molecules.
What this means is we can always think of the potential energy between two atoms as looking something like this:

The "ghost" particle represents a stationary atom, and the line represents the potential energy "surface" that another atom would see. From this graph, hopefully you can see that the moving atom would tend to fall towards the stationary atom until it just touches it, at which point it would stop. Since all atoms have some attractive force between them, and only the magnitude varies, we can keep this picture in our minds and just change the depth of the potential energy "well" to make the forces stronger or weaker.
Kinetic Energy
Let's modify the first potential energy surface just a little bit:

Now if I ask "where is the rock going to go?," It's a little bit tougher to answer. The reason is that you can tell the rock is "trapped" in the first little valley. Intuitively, you probably can see that if it had some velocity, or some kinetic energy, it could escape the first valley and would wind up in the second. Thinking about it this way, you can also see that even in the first picture, it would need a little bit of kinetic energy to get moving. You can also see that if either rock has a lot of kinetic energy, it will actually go past the deeper valley and wind up somewhere past the right side of the image.
What we can take away from this is that potential energy surfaces tell use where things want (I use the term very loosely) to go, while kinetic energy tells us whether they are able to get there.
Let's look at another microscopic picture:

Now the atoms from before are at their lowest potential energy. In order for them to come apart, you will need to give them some kinetic energy.
How do we give atoms kinetic energy? By increasing the temperature. Temperature is directly related to kinetic energy - as the temperature goes up, so does the average kinetic energy of every atom and molecule in a system.
By now you might be able to guess how increasing the temperature of water helps it to clean more effectively, but let's look at some details to be sure.
Solubility
We can take the microscopic picture of potential and kinetic energies and extract two important guidelines from it:

All atoms are "sticky," although some are stickier than others
Higher temperatures mean that atoms have larger kinetic energies

Going back to the coffee cup question, all we need to do now is think about how these will play out with the particular molecules you are looking at.
Coffee is a mixture of lots of different stuff - oils, water-soluble compounds, burnt hydrocarbons (for an old coffee cup), etc. Each of these things has a different "stickiness." Oils are not very sticky at all - the attractive forces between them are fairly weak. Water-soluble compounds are very "sticky" - they attract each other strongly because they have large charges. Since water molecules also have large charges, this is what makes water-soluble compounds water-soluble - they stick to water easily. Burnt hydrocarbons are not very sticky, sort of like oils.
Since molecules with large charges tend to stick to water molecules, we call them hydrophilic - meaning that they "love" water. Molecules that don't have large charges are called hydrophobic - they "fear" water. Although the name suggests they are repelled by water, it's important to know that there aren't actually any repelling forces between water and hydrophobic compounds - it's just that water likes itself so much, the hydrophobic compounds are excluded and wind up sticking to each other.
Going back to the dirty coffee cup, when we add water and start scrubbing, a bunch of stuff happens:
Hydrophilic Compounds
Hydrophilic compounds dissolve quickly in water because they stick to water pretty well compared to how well they stick to each other and to the cup. In the case where they stick to each other or the cup better than water, the difference isn't huge, so it doesn't take much kinetic energy to get them into the water. So, warm water makes them dissolve more easily.
Hydrophobic Compounds
Hydrophobic compounds (oils, burnt stuff, most stains) don't stick to the water. They stick to each other a little bit (remember that the forces are much weaker compared to water since the charges are very small), but water sticks to itself so well that the oils don't have a chance to get between the water molecules. We can scrub them, which will provide enough energy to knock them loose and allow the water to carry them away, but if we were to increase the kinetic energy as well by increasing the water temperature, we could overcome both the weaker forces holding the hydrophobic compounds together, while simultaneously giving the water molecules more mobility so they can move apart and let the hydrophobic compounds in. And so, warmer water makes it easier to wash away hydrophobic compounds as well.
Macroscopic View
We can tie this back to the original thermodynamics vs. kinetics discussion. If you increase the temperature of the water, the answer to the question "How much will dissolve" is "more." (That was the thermodynamics part). The answer to "How long will it take" is "not as long" (kinetics).
And as @anna said, there are other things you can do to make it even easier. Soap for example, is made of long chain molecules with one charged end and one uncharged end. This means one end is hydrophilic, while the other end is hydrophobic. When you add soap to the picture, the hydrophilic end goes into the water while the hydrophobic end tries to surround the oils and burnt stuff. The net result is little "bubbles" (called micelles) made up of soap molecules surrounding hydrophobic molecules that are in turn surrounded by water.
