It has to do with air pressure. Air moving from a higher to a lower elevation compresses, making the air warmer. Many times the difference is on the order of 5 degrees F per 1000 feet, which can create quite a difference- for example, if the Continental Divide averages around 12,000 feet in CO and the Plains are around 5000 feet, that's a 35 degree difference just from compression. There are of course other factors, but that's the basic reason.
As to the part of your question about why it's warmer than the air that has been sitting around at a given elevation for a while, it has to do with cool air sinking. At night, if it isn't windy, cooler air will layer out. So if it's 20 F in Denver on a calm morning, then a westerly wind kicks up from the mountains, you get warmer, compressed air invading the cooler air. Many times the temp can go up 30 F in a couple hours with the combination of a Chinook wind and mixing the layers out. This time of year, you can get what we call "two-coat days": perhaps 18 F (winter coat) at 6 AM, 50 F (spring coat) at 9 AM, and 68 F (no coat) at 2 PM.
Then again, you can get 8 F within a couple of days after 70 F (this happened Sat PM-Tues AM at Centennial Airport) when cold air rushes down the lee side of the mountains. Tough place to be a plant!!