Does an increase in pressure necessarily lead to an increase in temperature? Ideal gas law says that $pV = nRT$. So with compression, one way to add pressure which makes the volume smaller, can you actually increase the temperature?  

It does not make sense to me that you can increase temperature, that is, add to the kinetic energy of the molecules, simply by increasing pressure, pressure meaning the force exerted on the gas from its surroundings. Can someone please explain this contradiction?
I think what you are asking is "why can the temperature of the gas increase when you compress it, even if the cylinder is adiabatic so that no heat can enter the gas?"  When you move the piston to compress the gas, you are doing work on the gas at the interface with the piston.  The piston is moving toward the gas, and the molecules of gas that collide with the piston leave with a greater average velocity than when they arrived.  So their average kinetic energy is increasing.  If expansion were occurring, such that the piston were moving away from the gas, the colliding molecules would leave with lower average kinetic energy.