My chemistry teacher once explained it to me like below. Does anyone know how much truth there is to this explanation?
Temperature as measured by a thermometer or your finger is an average. Not every single molecule has the same temperature. The molecules constantly bounce around, smashing into each other, transferring heat to each other. By chance, some molecules will get hit in just the right way by other molecules to reach a very high temperature and then it evaporates. So there is constantly a gradient of temperatures among the molecules and the ones with the highest temperature are the ones evaporating, until there is no liquid left at all.
As the average temperature increases, the chance of some molecules reaching a high enough temperature also increases, so warm water evaporates faster than cold water.
This also explains why evaporation cools down (like when you sweat): the molecules with the highest temperature are the ones evaporating, so the average temperature decreases as those high-temperature molecules leave the system. Only the relatively colder molecules are left behind - thus it cools as a whole.