What is the difference between \mathbin vs. \mathrel?

From the name, \mathbin modifies the spacing around something so that it adheres to that of a binary operator, while \mathrel modifies the spacing to denote that of a binary relation. Here is an elementary approach at showcasing the difference:

\documentclass{article}
\begin{document}
\begin{tabular}{clc}
  \multicolumn{3}{c}{Relations} \\[5pt]
  \LaTeX & Typeset & width \\ \hline
  \verb|$x=x$| & $x=x$ & \setbox0=\hbox{$x=x$} \the\wd0 \\
  \verb|$x\mathbin{=}x$| & $x\mathbin{=}x$ & \setbox0=\hbox{$x\mathbin{=}x$} \the\wd0 \\
  \verb|$x\mathrel{=}x$| & $x\mathrel{=}x$ & \setbox0=\hbox{$x\mathrel{=}x$} \the\wd0 \\[10pt]
  \multicolumn{3}{c}{Binary operators} \\[5pt]
  \LaTeX & Typeset & width \\ \hline
  \verb|$x+x$| & $x+x$ & \setbox0=\hbox{$x+x$} \the\wd0 \\
  \verb|$x\mathbin{+}x$| & $x\mathbin{+}x$ & \setbox0=\hbox{$x\mathbin{+}x$} \the\wd0 \\
  \verb|$x\mathrel{+}x$| & $x\mathrel{+}x$ & \setbox0=\hbox{$x\mathrel{+}x$} \the\wd0
\end{tabular}
\end{document}​

Note the spacing around + matching that of \mathbin, while the spacing around = matches that of \mathrel.

From the TeXBook (Chapter 17: More about Math, p 154-):

Every math character is given an identifying code number between 0 and 4095, obtained by adding 256 times the family number to the position number. This is easily expressed in hexadecimal notation, using one hexadecimal digit for the family and two for the character; for example, \hex{24A} stands for character \hex{4A} in family 2. Each character is also assigned to one of eight classes, numbered 0 to 7, as follows:

Class 0: Ordinary (eg., /)
Class 1: Large operator (eg., \sum)
Class 2: Binary operation (eg., +)
Class 3: Relation (eg., =)
Class 4: Opening (eg., ()
Class 5: Closing (eg., ))
Class 6: Punctuation (eg., ,)
Class 7: Variable family (eg., x)

Classes 0 to 6 tell what "part of speech" the character belongs to, in math-printing language; class 7 is a special case [...]. The class number is multiplied by 4096 and added to the character number, and this is the same as making it the leading digit of a four-digit hexadecimal number.
...
TeX associates classes with subformulas as well as with individual characters. Thus, for example, you can treat a complex construction as if it were a binary operation or a relation, etc., if you want to. The commands \mathord, \mathop, \mathbin, \mathrel, \mathopen, \mathclose, and \mathpunct are used for this purpose; each of them is followed either by a single character or by a subformula in braces. For example, \mathopen\mathchar"1234 is equivalent to \mathchar"4234, because \mathopen forces class 4 (opening). In the formula $G\mathbin:H$, the colon is treated as a binary operation.
...
There's also an eighth classification, \mathinner, which is not normally used for individual symbols; fractions and \left...\right constructions are treated as "inner" subformulas, which means that they will be surrounded by additional space in certain circumstances. All other subformulas are generally treated as ordinary symbols, whether they are formed by \overline or \hbox or \vcenter or by simply being enclosed in braces. Thus, \mathord isn't really a necessary part of the TeX language; instead of typing $1\mathord,234$ you can get the same effect from $1{,}234$.

There are three main differences between \mathrel and \mathbin:

1. For optimal readability of math formulas, the more important elements must receive more space. That's why \mathrel (for math relations like =, <, >, etc.) receives a thick space (5/18th of an em) while \mathbin (for math binary operators like +, -, \oplus, etc.) receives a medium space (4/18th of an em). The difference is subtle, but enhances reading of formulas.

2. \mathbin and \mathrel behave differently relative to shrinking or stretching. When TeX does not have enough space available on a given line, it will contract a \mathbin space while it will never do so for a \mathrel space. When TeX has too much space available on a given line, it will stretch both. Here are the values used (1mu = 1/18th em):

\medmuskip = 4mu plus 2mu minus 4mu
\thickmuskip = 5mu plus 5mu

Here's an example of both situations:

As you can see, in a shrinking situation, + has no space around it, but in stretching situations, = can extend much more than + (10/18th em vs 6/18th em).

3. Finally, \mathbin and \mathrel behave differently in different contexts. For example, $A = -B$ works as expected (no space between - and B) but $A = \mathrel{-}B$ would not:

This is only one example of what can go wrong with the spacing if the type of the symbol is incorrect.

Comparison to \mathop: contrary to \mathbin and \mathrel, \mathop is for things like \sum, \cos, \ln etc. and only inserts a thin space (3/18th em, no shrinking or stretching) and, just as \mathbin and \mathrel, has special spacing rules to make it spaced correctly in most context.