What does "upvalue" mean in Mathematica and when to use them?

Actually, g /: f[g[x_]] := h[x] is not equivalent to f[g[x_]] := h[x]. The latter associates the definition with f, while TagSet (/:) and UpSet (^= and its delayed version, ^:=) associate the definition with g. This is a crucial difference and can be illustrated by a simple example. Let's say you want to have a set of variables that obey modulo 5 addition, i.e. 6 + 7 mod 5 = 3. So, we want anything with Head mod to behave correctly. Initially, we'd think that

a_mod + b_mod := mod@Mod[a + b, 5]

would work. But, it generates the error

SetDelayed::write : Tag Plus in a_mod + b_mod is Protected.

We could remove Unprotect Plus and our definition would then work, but this may cause problems with other definitions and as Plus accumulates more definitions, it would slow down. Alternatively, we can associate the addition property with the mod object itself via TagSet

mod /: mod[a_] + mod[b_] := mod @ Mod[a + b, 5]

or UpSetDelayed

mod[a_] + mod[b_] ^:= mod @ Mod[a + b, 5]

Setting an upvalue is somewhat more correct from a conceptual point of view since mod is the one with the different property.

There are a couple of issues to be aware of. First, the upvalue mechanism can only scan one level deep, i.e. Plus[a_mod, b_mod] is fine, but Exp[Plus[a_mod, b_mod]] will throw an error. This may require you to get creative with an intermediate type. Secondly, from a coding perspective UpSetDelayed is easier to write, but occasionally there is some ambiguity as to which Head is the upvalue associated with. TagSet handles that by explicitly naming the appropriate Head, and in general, it is what I tend to prefer over UpSet.

Some of Mathematica's operators do not have any behavior associated with them, so they're not protected. For these operators, you can define functions as you wish. For instance, I've defined

a_ \[CircleTimes] b_ := KroneckerProduct[a,b]
a_ \[CircleTimes] b_ \[CircleTimes] c__ := a \[CircleTimes] ( b \[CircleTimes] c )

and

a_ \[CirclePlus] b__ := BlockDiagonal[{a,b}]

to provide convenient shorthand notations for matrix operations that I use a lot.

My example above was a little contrived, but there are a number of times UpValues have come in handy. For example, I found that I needed a symbolic form for the complex roots of unity that behaved appropriately under multiplication and exponentiation.

Example: A straightforward and useful example is marking a Symbol as Real:

makeReal[a__Symbol] := (
     # /: Element[#, Reals] := True; 
     # /: Im[#] := 0; 
     # /: Re[#] := #;
     # /: Abs[#] := Sign[#] #;
     # /: Arg[#] := Piecewise[{{0, Sign[#] >= 0}, {Pi, Sign[#] < 0}}]
   ) & /@ List[a]

Note the use of TagSet as Element[ a, Reals ] ^:= True would be ambiguous. What would the rule be attached to a or Reals? Also, if we wanted a positive real number, we could set Arg[#]:=0 which allows Simplify to behave as expected, e.g. Simplify[Sqrt[a^2]] == a.

In addition to the excellent answer by @rcollyer, I'd like to emphasize a few other important things about UpValues.

Soft/local redefinition of system and other functions

One very important aspect is that they allow you to "softly" overload some system functions only on certain symbols. The importance of this was pointed out by @rcollyer, but can not be emphasized enough - this makes the effect of your code local, and drastically reduces the chances that your code can globally interact and affect some other part of the system or other piece of user-defined code, unlike when you Unprotect system symbols and add some DownValues to them.

In addition to being safe and local, such redefinitions may also be quite general, if one uses constructs like yourSymbol/:f_[_yourSymbol,rest___]:=.... These should be used with care, but can sometimes give very concise and simple solutions. Here is one example where one code can be used to "overload" several system functions at once, giving them additional non-trivial functionality.

Order of evaluation

The next point is evaluation. The common statement you can encounter is that "UpValues are applied before DownValues". This must be clarified: for f[g[args]] it means that UpValues for g are applied before DownValues for f, provided that the evaluation process already went all they way "down" to innermost parts, and then went back "up". In particular, it does not mean that UpValues for g will be applied before DownValues for g - if g[args] can evaluate inside f because g has appropriate DownValues, it will (unless f has one of the Hold-attributes), and the presence of UpValues won't prevent that, because (for standard evaluation), evaluation of g[args] happens before the evaluation of f[result-of-evaluation-of g[args]]. For example, here:

In[58]:= 
ClearAll[f, g];
f[x_] := x^2;
g /: f[g[x_]] := Sin[g[x]];
g[x_] := Cos[x];

In[62]:= f[g[y]]
Out[62]= Cos[y]^2

The UpValues for g had no chance to apply, since g[y] is transformed into Cos[y] at the previous evaluation step. The situation would be different for non-standard evaluation - either if we give f attributes HoldAll or HoldFirst, or if we wrap g[y] in Unevaluated - in both cases we give the evaluator the instruction to skip the evaluation of g[y]:

In[63]:= f[Unevaluated[g[y]]]

Out[63]= Sin[Cos[y]]

Escaping Hold-attributes

This one is related to the previous point: one should be aware that search for UpValues is performed even inside heads with Hold- attributes, and therefore, UpValue-based definitions may evaluate even when similarly-looking DownValue - based ones won't. Example:

In[64]:= ClearAll[f,ff];
f[x_]:=Print["Evaluated"];
ff/:h_[ff[x_]]:=Print["Evaluated"];

In[67]:= Hold[f[1]]
Out[67]= Hold[f[1]]

In[68]:= Hold[ff[1]]
During evaluation of In[68]:= Evaluated

If one wants to absolutely prevent the search for UpValues, one should give a function the HoldAllComplete attribute. For example:

In[69]:= {HoldComplete[f[1]],HoldComplete[ff[1]]}
Out[69]= {HoldComplete[f[1]],HoldComplete[ff[1]]}

Level-1 tag depth restriction

This was already mentioned by @rcollyer. This limitation was introduced for efficiency of the pattern-matcher/evaluator. I just want to stress one important and rather non-obvious consequence of it: it looks like you can not use UpValues to overload assignment (Set operator) so that it would work on variables assigned to objects of some specific type you introduce. Here is an attempt:

In[74]:= 
ClearAll[a,myType,myCustomCode,newValue];
myType/:Set[var_myType,rhs_]:=myCustomCode;

This seems to work. But let us try:

In[79]:= a = myType[1, 2, 3];
a = newValue;
a

Out[81]= newValue

It does not do what we want, obviously. The problem is that Set holds its l.h.s., so by the time the pattern-matching happens, it only has the symbol a, not its value. And because we can not associate the definition with tags deeper than on the first level of the expression, the following won't work either:

ClearAll[a,myType,myCustomCode,newValue];
myType/:Set[var_,rhs_]/;MatchQ[var,_myType]:=myCustomCode;
TagSetDelayed::tagpos: Tag myType in (var_=rhs_)/;MatchQ[var,_myType]
  is too deep for an assigned rule to be found. >>

To my knowledge, UpValues can not be used to solve this problem, which is a pity, since having a usual = syntax with custom assignment code for various data types would be convenient. For a similar discussion, see e.g. this post. This situation is not unique for Set - the same would hold for any function that holds the argument that you want to use for your UpValue-based definition.

Some differences between UpSet and TagSet, UpSetDelayed and TagSetDelayed

It is worth knowing that when you use UpSet or UpSetDelayed, then all tags at level 1 acquire additional definitions (rules). For example:

Clear[a,b];
Plus[a,b]^:=1;

?a
Global`a
a/:a+b:=1

?b
Global`b
b/:a+b:=1

In contrast with this, TagSet and TagSetDelayed are more precise:

ClearAll[a,b];
a/:Plus[a,b]:=1;

?a
Global`a
a/:a+b:=1

?b
Global`b

In my experience, the latter behavior is usually more desirable, so in most cases I prefer TagSet or TagSetDelayed over UpSet or UpSetDelayed.

Rcollyer has already given an excellent answer but here is an example of when you might use UpValues: when you are defining a particular data structure, with its own Head, and you want to defining how built in operations like arithmetic work with that structure. I once did this for a timeSeries data structure where, for example, addition would match up the dates in the first columns and add the corresponding pairs of values in the second columns. Adding T * 2 vectors with dates in the first column would give nonsense dates if you hadn't defined such an operation using an UpValue.