If cold air is denser then why is compression associated with atmospheric heating? If cold air is denser than warm air then I would assume compression of air would cause air to cool and expansion would cause air to heat up. Why is it the opposite?
 A: Nothing compresses air to make it colder.  Temperature is based on movement of molecules.  As air radiates heat, the molecules move slower and slower, reaching liquid state if cooling continues, and eventually frozen solid. (thank goodness for the sun).  Slower moving molecules generally have greater density because they do not push each other apart as much.
From this data we can deduce that "temperature" or warmth is based on emission of heat, caused by number of molecular collisions and the kinetic energy of each collision. (Now that is starting to sound like something to do with aviation, no?)
This in turn is based on the energy input into the system.
Compression (within a cylinder) increases the number of collisions, which increases temperature.  But compressed air will cool, and if released to ambient pressure, will be cooler.
Temperature of air at the same pressure can be raised by input of solar radiation, causing the molecules to move faster.  This raises pressure within a closed system, but lowers density in an open system.
In an open system (such as a hot air balloon) pressure remains the same, density changes based on temperature.  In a closed system pressure changes with temperature.  Density cannot change unless the volume is changed by physical compression or expansion.
A: This all depends upon the context. In a constant volume and pressure environment, a unit volume of cold air will be denser than a unit volume of warmer air.  In an adiabatic compression, the work done to compress a unit mass to air into a smaller volume will be stored in the gas as internal energy ie heat.  Given that air can be modeled very accurately as an ideal gas, this relationship may be expressed as P = pRT. This is why air heats up when compressed by work applied to a closed system.
A: In order to fully describe the air for the purposes of this question, we need three properties: the temperature $T$, the density $\rho$, and, the one you didn't explicitly mention in your question, the pressure $P$.  These three properties are related in the following way: $$P\propto \rho T.$$
This relationship explains your first observation: that cold air is denser.  For any given value of $P$ (ambient atmospheric pressure, say), if $T$ decreases then $\rho$ must increase and vice versa.
What happens in second situation--compression of the air--is that all three variables, $P$, $\rho$, and $T$, change at the same time.  You can't determine from the relationship $P\propto \rho T$ alone what happens, because you're no longer holding any one of them constant. You need another relationship.  When you do the compression without adding or removing any heat it so happens that: $$P\propto \rho^{7/5}.$$
This says that when you squish the gas, increasing its density, you increase the pressure even more (the exponent determines how much more; $7/5$ is the amount for diatomic gasses like $\text{O}_2$ and $\text{N}_2$). Looking back at the first equation, that means that you also increase the temperature.
These two expression tell you $what$ happens, but not $why$. The reason can be understood in terms of energy. The total internal energy of a collection of gas molecules depends only on its temperature. When you compress a gas, you are doing work on it: adding energy to it.  If no energy is removed by other means, the internal energy must increase. So compressing a gas increases its temperature.
