The swimming method
One of the best ways to cool off is to go for a swim. This can be done in a swimming pool, in a nearby river or lake, or at the beach. However, you may not be able to do this, for a variety of reasons.¹

The water hose method
Take a water hose, hold the nozzle over your head, and turn it on, spraying down towards you. You may want to leave to sprayer thingy off, but if you do keep it on, be sure to set it to a spray that is not so powerful as to be painful when it hits you. Soaker is good; so is any misting one.

The water sprayer method
Get ahold of one off those water sprayers, such as the ones used for cleaning products(but don't use one of those, or if you do, wash it out *really* well with hot water), fill it with nice cold water, and carry it around. Whenever you feel overheated, spray yourself in the face with the water.

The fan method
Three ways to do this:#1 Find a large fan and stand in front of it.#2 Carry a small fan around with you. The ones that clip onto desks and such are good for this. #3Make a paper fan and wave it at your face ever so often. You make the fan by taking a peice of paper and folding it accordian-style, that is, first one way than the other. On edge it should look like a zig-zag. Then, you staple or fold over one end. This is by far probably the least effective way of cooling off, its advantages being that it is very portable, takes little work to prepare, does not make you look silly using it, and does not involve getting wet and thus looking disreputable. Either of the first two can be combined with the water sprayer method by simply spraying water into the fan blades, which makes them more effective.

The air-conditioned place method
This method is quite simple. Just find an air-conditioned place, such as a library, museum, or grocery store, and hang out there for awhile. Most places that have computers are good for this as they have fans to cool them off.

The sprinkler method
Run through a sprinkler while it is on. While sort of undignified, this is a great way to cool off.

The cold shower method
Take a very cold shower. Do not use any hot water. This is very effective for cooling off, however you might want to know...

What to expect:

At first you stop breathing just from the shock of the cold water. Then you start to hyperventalate. After a few seconds you will start breathing normally again, as you adjust to the shock. A cold shower usually takes much less time than a hot one, since cold water is not especially comfortable, and hot water is. You will, though, be very comfortable after you get out, since it is still a hot day and you are cool, having just had all your body heat sucked out by cold water. An added advantage is that this can be done easily in the privacy of your own home, and is not at all messy. A disadvantage is that you do need to be at home, or somewhere else you can take a shower. It can't be done, say, on a trip to the zoo or(usually) in the office when the AC has broken.²

The water hose-and-trash can method
Go out and get a new, unused trash can(or you can take an old one and wash it out really well.). Make sure you can fit inside and get out relatively easily. Fill it with water from a garden hose. Then get in. You may want to change into a swimsuit for this, or you may just want to wear regular clothes so you will be cool all day. It's up to you.

The hat method
Take one baseball cap, ³, and fill it with water. Then put it on, quickly.

A note on hats:

Since most body heat is lost through the head, wearing a hat is a good way to keep you warm. While this is fine in the winter, in the summer it can be a very large irritation. Therefore, don't wear a hat unless it's actually cooler than your head.

In a car
Sometimes you will come back to your car after leaving it in the parking lot for several hours only to find that it is about 20 degrees hotter than the outside air. Naturally you do not want to get in until it is cooler. There are a number of things you can do to remedy this: You can open all the doors(and back windows, if your car is a two-door) and wait for the hot air to escape. This method is almost always available, no matter what kind of car you have. If your car has a sunroof that is openable, open it all the way. Since heat rises, and the sunroof is in the top of the car, this creates something called the chimney effect which sucks out the heat quicker. If your car is a convertable, and the top isn't broken, put the top down. One thing you do not want to do is just get in the car and turn the air conditioning on all the way. This creates a strain on the engine, overheating it. The worst situation for this is when you are stuck in a traffic jam. In that case, if the engine overheats, open all the windows, the sunroof if you have one, and turn the heat on. This will cool the engine off, but will make it terribly uncomfortable. Then your best bet is to find an unimportant piece of paper and make a fan out of it and wave it at your face. Or you can take a book(such as the owner's manual, which many people keep in the glove compartment because that's where the dealership put it and they've never touched it) and flip the pages, creating a small wind.

Hot Peppers
Eating hot peppers can actually cool you off, as it makes you sweat more.