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 increase 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.
Many natural gases (including CO2, CH4, NH3, NO2) are greenhouse gases, but artificial Super Greenhouse Gases can be created which are very long lived in the atmosphere, and will warm the planet hundreds or thousands of times more effectively than carbon dioxide (CO2). People have estimated that it would cost half a billion dollars per year to warm the planet with such gases.
Water is a powerful greenhouse gas, but if its concentration rises, it soon precipitates out of the atmosphere. Thus though it contributes to global warming, it is a constant and does not force global warming.
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.