TeX's tables are strange beasts with respect to expansion. Here is a plain TeX table with a right-aligned and a left-aligned columns
\halign{\hfil #&#\hfil \cr
a & bc \cr
de & f \cr}
The first line is the "preamble", which tells TeX what to do with the material in each cell, represented by #. So the first line becomes \hfil a&bc\hfil \cr. The \hfil stand for blank space that can stretch to fill an arbitrary distance, hence aligning the cell contents.
Taking this approach as given, let us try to invent how rules could be added to the language, with Knuth's hat on. [Admittedly, I'm likely to err in some of the resons that led Knuth and later engine developpers to make various decisions, but I think my picture is consistent, albeit full of anachronisms.]
Rules should be added between two lines, in other words, just after \cr. We postulate a hypothetical \hline, added after the \cr to produce a horizontal rule:
% Fake TeX code
\halign{\hfil #&#\hfil \cr
a & bc\cr
\hline
de & f\cr
\hline}
In the approach described so far, TeX would take \hline de as the cell's contents, and the second line would become \hfil \hline de&f\hfil\cr. In that particular case, we could still manage by making \hline insert material before the current line. But the trailing \hline is problematic: TeX would realize too late that there is no cell here: it would insert \hfil for the start of the first cell's preamble, then see \hline, insert the rule before the current line, see }, and have to back up somehow the \hfil.
A saner approach would be that when TeX sees \cr, it looks at what follows for an \hline. Should \hline be a primitive? That would only allow for the types of rules or inter-row material which have been hard-coded in the engine itself. No. A much better solution, which Knuth chose, is to allow for arbitrary material, with \noalign. Then there is no need to also provide \hline, which is simply a horizontal rule (\hrule) which is not aligned. So the real plain TeX way of having a line (well, two) is
\halign{#&#\cr
a & b \cr
\noalign{\hrule}
c & d \cr
\noalign{\hrule}}
Most will complain that the rules are too close to the text, but we are interested for now in expansion issues, not typography. Naturally, one may want to provide a shorthand for \noalign{\hrule}, say, \hline:
\def\hline{\noalign{\hrule}}
\halign{\hfil #&#\hfil\cr
a & b \cr \hline
c & d \cr \hline}
Again, we end up with the question of how TeX can know that this \hline macro hides a \noalign, and how TeX knows that it shouldn't just insert \hfil right away. The answer is that to find the \noalign, TeX expands macros after \cr, before inserting the material from the preamble. The same happens at each cell to look for \omit, but I won't delve on that.
This leads to problems: for instance, a macro which behaves differently in math mode than in text mode, should not start with \ifmmode but with \relax\ifmmode.
\def\foo{\relax\ifmmode x^2\else the square of $x$\fi}
\halign{\hfil $#$\hfil &\hfil $#$\hfil \cr
\foo & y^2 \cr
z-2 & t\cr}
TeX expands the first token after the \cr, which is \foo, then sees \relax. This stops the expansion, it is not \noalign nor \omit, so the preamble is inserted, entering math mode. The \ifmmode test is then performed. Without the \relax, \ifmmode would be evaluated before the preamble is inserted, and be false.
To help fight against this expansion, the eTeX programmers decided (in version 2, according to the eTeX manual) that \protected macros would stop the expansion in this situation. This is somewhat inconsistent with how eTeX expands in other full-expansion-from-the-left settings such as \romannumeral-`q. In Martin's case (see his answer to the current question), this ends up being very useful since he can stop the expansion using a protected macro. In other cases (see some of Peter Grill's questions, for instance one about how to provide a wrapper for \cmidrule), we would like TeX to try harder to find the hidden \noalign.
