An evaporative cooler uses a combination of a water source and a fan to blow air that has moisture (water that has evaporated) in it  into an area.  In order for water to evaporate, it needs a heat source.  An evaporative cooler uses warm air as the heat source to evaporate the water.  When the water evaporates, it sucks heat from the air...and just like that you have cooler air!

This is the same principle your body uses to keep yourself cool.  Sweat on your skins sucks the heat away from your body in order to evaporate, thus leaving your body cooler (and some salt behind).

But there is one key thing to remember when analyzing evaporative coolers: They don't work too well in humid environments!

From the EERE site on evaporative coolers (which mainly focuses on evaporative coolers you install for your whole home):

In low-humidity areas, evaporating water into the air provides a natural and energy-efficient means of cooling. Evaporative coolers, also called swamp coolers, rely on this principle, cooling outdoor air by passing it over water-saturated pads, causing the water to evaporate into it. The 15°–40°F-cooler air is then directed into the home, and pushes warmer air out through windows.

It seems that evaporative coolers work best in the Western U.S., where it isn't as humid, but I wanted a little more quantitative analysis. Luckily, the California Energy Commission has a nice section on Evaporative Coolers and they have a chart that was originally done by Ed Phillips for the Arizona Almanac:

By looking at this chart, you can see that if you have a whole home evaporative cooler (which pulls in outside air) , the outside air temp in the summer regularly gets around 90°F and your humidity levels stay above 50%, you are going to have a hard time cooling off!  April Holladay explains this nicely on Wonder Quest for the question, "When is it too humid for swamp coolers":

The swamp cooler cools the outside air and blows the cooler air into the house.  The green range of cool air temperatures on the graph shows the conditions when the swamp cooler works best — lowering house temperature to the 70's (22 - 26 C).

Humidity makes a difference.  At 50 % humidity, an evaporative cooler can lower the air coming into the cooler by about 10 degrees (6 degrees C).  But at 10 % humidity, the cooler can plummet temperatures by about 20 to 30 degrees (13 to 14 degrees C)

So, for example, if the outside temperature is 90 degrees F (32 C) and the relative humidity is 50%, then the swamp cooler can cool the house to 79 degrees (26 C).  Moreover, at 90 degrees (32 C) outside and only 10% humidity, the house temperature drops to 67 degrees (19 C).

On the other hand, when the outside temperature soars to 100 degrees (38 C), we're in trouble if the humidity is much above 25%.  When the swamp cooler doesn't work well depends both on outside temperature and humidity.  The higher the outside temperature, the lower the humidity must be to drop the house temperature into the cool 70's.

By the way, the swamp cooler sends a breeze through the house so the air temperature feels about five degrees cooler that it is.

But there aren't only whole home evaporative coolers, there are also portable ones.  One manufacturer is KuulAire (ignore the bad name) and they show how their unit works on their webpage.  One of the KuulAire PACKA50 Portable Evaporative Cooling Unit is for sale on Amazon for $199.95, but there are several different sizes.

One unit that is a semi-evaporative cooler is the "free" mira-cool units.  I'm a tad bit skeptical of these units if only for their crazy advertisements.

Finally, one of the best summary's on evaporative cooling is found on Wikipedia.  It includes the benefits and drawbacks of using evaporative coolers.