To expand on shuttle_guy's answer, think of what happens when you fire a gun. The bullet flies in one direction, and the gun recoils in the opposite direction. This is not because the bullet is pushing on the air, but is because "for every action, there is an equal and opposite reaction." The gun puts a large force on the bullet to shoot it out, and the bullet puts an equal and opposite force on the gun. It would happen just the same in a vacuum as it does normally.<br /><br />The same works with rockets, but instead of shooting bullets, they are shooting propellant. The rocket puts a force on the propellant by combusting it and allowing it to expand at great velocity out a nozzle. The propellant places an equal and opposite force on the rocket, thrusting it forward.