Evaporative cooling relies on the amount of energy it takes to excite water from a liquid to a gaseous state.  If you increase the humidity by say, 10% that means you are actively moving water into a gaseous state.  This transition from liquid to gas requires energy, which lowers the temperature of the air.