Greenhouse gases are gases which are more transparent in the visual spectrum than in the thermal (infrared) spectrum. In the atmosphere of a planet, these gases will cause a higher surface temperature.
Because the sun's emissions peak in the visual range, visible light passes through such gas relatively unhindered and heats up the surface below. When the planet re-emits the energy as blackbody radiation, it is in the infrared range due to the planet's comparatively low temperature.
The greenhouse gases are opaque at these frequencies and will absorb much of the radiation, heating up in the process. Alternatively, they may be reflective in the thermal range and simply reflect the radiation back down. This results in a higher average surface temperature than without the greenhouse gases.
Beyond the Earth
For greatest effect, the greenhouse gas must be as opaque as possible in the range of blackbody radiation from the planet and as transparent as possible in the range of its star's peak output. Since Mars has the same sun as the Earth and a similar (if lower) temperature, the effectiveness of greenhouse gasses would not be severely different.