Fierz identities are discussed in the wikipedia article:
http://en.wikipedia.org/wiki/Fierz_identity
but the article doesn't give any derivation. The article implies that they arise from the blade structure of a Clifford algebra.
Some notes to be deleted after we have a solution:
They seem to arise in QFT calculations and (perhaps as a result) they can always be put into "pure density matrix" form. That is, the spinors can be arranged to appear in an order that makes them natural for a trace operation.
For example, with $U,V,W$ as unspecified operators and $\theta,\psi$ as spinors, one might have:
$(\bar{\theta}U\theta)(\bar{\psi} W\theta)(\bar{\theta} V\psi)$
where the unbarred and barred spinors do not always match as they do in "$…\theta)(\bar{\theta}…$". But this can be rearranged to give:
$(\bar{\theta}U\theta)(\bar{\theta} V\psi)(\bar{\psi} W\theta)$
One can then turn the $\psi\bar{\psi}$ type elements into (almost) pure density matrices and treat the problem as one of computing traces:
$\textrm{tr} [ (\theta\bar{\theta}U\theta\bar{\theta} V\psi\bar{\psi} W ]$
And then one can use various properties such as the fact that with pure density matrices such as $|a\rangle\langle a|^2 = |a\rangle\langle a|$ one has that anything that begins and ends with such a thing has to be a complex multiple of the pure density matrix.
This would give the Fierz identities without explicitly looking at the blade structure of the Clifford algebra and that is very suspicious to me. I doubt it works.
On a previous question: Some Majorana fermion identities I intuitively convinced myself that Fierz identities could be established this way (and some very smart people seemed to agree) but when I tried to solve that problem this way I quickly was buried in unsuccessful calculations. Now it could be that that particular problem couldn't easily be so attacked, or my method was misapplied, etc.; I'm not sure.
Best Answer
I always thought of Fierz identities as a kind of completeness relation (*) for products of spinors. To use the bra-ket notation: $$|a\rangle\langle b| = \sum k_i \langle b|M_i|a\rangle M_i$$ for some convenient trace orthogonal basis.
To find the $k_i$ for the specific basis and space that you're working in, you multiply by some $M_j$ and take the trace: $$ tr(M_j |a\rangle\langle b|) = \langle b|M_j|a\rangle = \sum_i k_i tr( M_i M_j ) \langle b|M_i|a\rangle $$ since the basis is orthogonal with respect to the trace, we see that $k_i^{-1} = tr( M_i M_i )$.
This is then used to prove the Fierz identities as $$ \langle a|U|b\rangle \langle c|V|d\rangle = \sum_i\langle a|U (k_i \langle c|M_i|b\rangle M_i) V|d\rangle = \sum_i k_i \langle c|M_i|b\rangle\langle a|U M_i V|d\rangle $$
Thus you get your Fierz rearrangements. Note that depending on your definitions, if you're deriving the Fierz identities for anticommuting spinors, then you might have a sign factor in the first trace formula and definition of $k_i$ that I gave.
The standard Fierz identities are for 4-dimensional spinors, with the basis of gamma matrices $$ 1\,,\quad \gamma_\mu\,,\quad \Sigma_{\mu\nu}\;(\mu<\nu)\,,\quad \gamma_5\gamma_\mu\,,\quad \gamma_5 $$ which has $1 + 4 + 6 + 4 + 1 = 16$ elements, which is what you'd expect for 4*4 matrices. The basis elements are normally on both the left and right hand side of the Fierz identity. The traces for the above basis can be calculated from the Wikipedia Gamma matrix page.
In the previous question, Some Majorana fermion identities, I used 2-component notation to check the identities. This is convenient since the completeness relation is really simple. Using the conventions of Buchbinder and Kuzenko the spinor completeness relation is simply the decomposition into an antisymmetric and symmetric part: $$ \psi_\alpha \chi_\beta = \frac12\varepsilon_{\alpha\beta}\psi\chi - \frac12(\sigma^{ab})_{\alpha\beta}\psi\sigma_{ab}\chi \,, $$ and similarly for the dotted-spinors (complex conjugate representation). This means that you don't need a table of coefficients to do Fierz rearrangements, all the steps fit easily in your memory.
I'm not sure what the best reference for Fierz identities is. Maybe have a look at Generalized Fierz identities and references within.
Footnote (*)
You can also think of the completeness relation purely in terms of the matrices. This is an alternate approach to derive the Fierz identities and is the one used in Generalized Fierz identities.