As a condiment, wasabi is available in three forms:

  1. paste (aka tube)
    This is the most convenient form, and is very common for household use. In Japan, a house without a tube of wasabi in the refrigerator would be like an American house with no ketchup. Take-out sushi often includes a small packet of wasabi paste. Most pre-made pastes contain little or no real wasabi.
  2. powdered
    Dried, finely powdered, and mixed with starches, this product is kept in an air-tight can and rehydrated with water to produce the thick wasabi used in most sushi restaurants. This form provides the best adhesive capabilities, and is often formed into decorative shapes such as flowers and leaves. On the other hand, it does not dissolve well. It also loses potency soon after rehydrating, so it should be used quickly. Many powders contain little or no wasabi, and contain other spices such as western horseradish and mustard.
  3. freshly grated
    Very expensive within Japan, real wasabi root is often difficult or impossible to obtain overseas. This is obviously the most authentic type. The flavor is generally milder and rounder than powdered wasabi. Once grated, it takes several minutes to reach its full flavor. Wasabi should be used within half an hour or so of grating or the flavor will be lost; the root itself will keep for about a month in a cool, dark place.

Note that the Japanese refer to horseradish as a type of wasabi (seiyou wasabi, or "western wasabi"), so even if your wasabi says "Made in Japan" and "Wasabi" on it, it may contain horseradish. The Japanese word to discriminate between wasabia japonica and just any old wasabi is hon wasabi, or "true wasabi." Many packages say "hon wasabi iri", or "contains real wasabi", but they generally neglect to say the amount, which is generally just enough to give the vague texture and aroma of wasabi.

Wasabi is most commonly known as a condiment for sushi and sashimi. Appropriately enough, in itamae-lingo, this pungent, aromatic root is referred to as "namida", or "tears".

Sashimi

Wasabi is almost always served with sashimi of all types. The amount to use is up to the diner, but generally, one should use more for oilier and stronger-tasting koi-mono, such as katsuo (bonito), saba (mackerel), and toro (fatty cuts of tuna), and less for lighter usui-mono such as tai (snapper) and hotate (scallop).

To season the piece of sashimi, pick up a bit of wasabi with the tips of your chopsticks, pick up the slice of sashimi, then dip it into a light soy sauce.

Sushi

The way to use wasabi with sushi depends on the type of sushi, method of preparation, and of course, the diner's preference. Often, the chef will include a thin layer of wasabi in nigiri-zushi, between the topping and the rice. This serves many purposes -- to add flavor and help to mask any unpleasant fishy taste, to help to bind the sushi together, and to prevent bacterial growth. In this case, it may not be necessary to add wasabi at all. Wasabi is not always served alongside sushi, some chefs might even take offense if you decide that the amount they have added isn't just right.

Many people, especially young children, don't like the characteristic pungent taste of wasabi. To order sushi without wasabi in Japan, use the phrase "wasabi-nuki".

Now that sushi has become an international cuisine, the use of wasabi varies around the globe. Even within Japan, the "one correct method" is hotly debated by connoiseurs, chefs, and variety show stars alike. One chef recommends the following method to American diners:

When eating nigiri-zushi, it is traditional to use your hands and wipe them on a towel. You may also use chopsticks. Take a dab of wasabi on the tip of the chopstick, gently pick up a piece of sushi, and dip the end of the topping in the bowl of soy sauce. Do not dip the rice side of the sushi in the soy as you will simply taste soy, rather than the flavors of both rice and topping. Put the sushi in your mouth with the topping side down--so the fish meets your taste buds. (Do not mix the wasabi in the soy sauce, as you will drown the sushi with the flavor of the wasabi.)
Source: Sushi, by Ryuichi Yoshii. Emphasis is mine.
This is a CST Approved use of copyrighted material.

As respected noder 1010011010 notes above, some prefer a more wasabi-centered approach to their dipping; the Japanese term for a mix of soy sauce and ground wasabi is wasabi-jouyu.

There are a few more writeups about using wasabi in and on sushi at the Everything Sushi Guide.

Wasabi in other Japanese dishes

When you say wasabi, most people automatically associate the word with sushi, but there are many other uses in Japanese cuisine.

  • Both the root and the heart-shaped leaves can be pickled, normally as a shiozuke. Not nearly as spicy as it sounds, this is a refreshing spring dish.
  • Japanese summers wouldn't be the same without the tang of wasabi in the dipping sauce for zaru-soba, buckwheat noodles served cold.
  • Nothing warms you up after a cold autumn evening like tucking into a bowl of wasabi ochazuke.
  • Wasabi is also used to flavor traditional snacks, such as some types of senbei, kaki no tane, wasabi peas, or preserved ika-wasabi. It's also in a lot of non-traditional snacks, like Calbee's unforgettable Wasabi Potato Chips.

I'm sure that some inventive souls have come up with ways to include wasabi in other cuisines, as well. (See esteemed noder arcanamundi's writeup below, and sensei's Special Sauce.)

Wasabi for health

Wasabi has been used by the Japanese for over 900 years, and has long been thought to prevent illness, especially when eaten with raw foods. Recent research indicates that there may be substantial benefits to regularly consuming wasabi, including the ability to fight stomach cancer. It also acts as an antimicrobic, stopping the growth of various bacteria, and helping to prevent food poisoning and tooth decay. As an anti-inflammatory, it may help to relieve asthma, and its anticoagulant properties are effective against blood clots. (Archer, 2001)

(Note: As an asthmatic, let me clear up the point that inhaling wasabi fumes during an asthma attack is a very bad idea.)

The active ingredient in many of wasabi's medical properties is isothiocyanate compunds. Depree, Howard, and Savage (1999) found that these compounds act very quickly and at low concentrations, warranting further research into developing wasabi-based medicinal applications.

And lastly, few would disagree that wasabi can certainly clear the sinuses.

REFERENCES:
DEPREE, J.; SAVAGE, G.P.; HOWARD, T.M. Flavour and pharmaceutical properties of the volatile sulfur compounds of Wasabi (Wasabia japonica). Food Research International 31: 329-337, 1999.
ARCHER, S. Wasabia Japonica. City Farmer Office of Urban Agriculture. Updated July 11, 2001. Accessed September 19, 2003. Available online at http://www.cityfarmer.org/wasabi.html