I don't understand thermodynamics too well, but here's what I figure: A rubber band is made up of polymers, long chainlike molecules that can twist in a number of different directions at each bond. With three mer units, the molecule can't bend too much, but with tens of thousands of mer units the polymer's basically just like a piece of string. For each polymer, there's a finite number of states it can be in. There's much, much more crumpled states than organized states. An organized state would be one where the rubber band is stretched so that its polymers line up. The random vibrations of the polymers cause it to change states frequently, and since there are more crumpled states than aligned states, the polymers tend to a crumpled state and the rubber tends to be unstretched. When you stretch the rubber band, you're fighting its polymers' tendencies to remain in a crumpled state, so you feel a force. If you heat rubber (not hot enough to cause a chemical change), its polymers vibrate more strongly, and they have an even stronger tendency to return to a crumpled state, causing a higher restoring force for hot rubber than cooler rubber, the opposite it would be for metals.
If we're talking about a rubber spring, then the answer seems pretty clear: when you stretch it, you create order on a microscopic level, which I assume means the entropy of the system is lowered. There's probably a similar answer that applies to all elastic materials, but I don't know what it is.
