How to motivate the skein relations? I am teaching an advanced undergraduate class on topology. We are doing introductory knot theory at the moment. One of my students asked how do we know to use this skein relation to compute all these wonderful polynomial invariants of knots. 
I was not trained as a knot theorist, so I was at loss. Intuitively  it does not seem to be that powerful, because it is not clear (to me at least) that you can always pick a recursive relation involving simpler knots. Could somebody help me motivating my students here? In other words,
Why are the skein relations so useful for computing polynomial invariants of knots, and when did people realize that is the case? 
Thanks. 
 A: Regarding "when", it was Alexander, in his paper on what we call the Alexander polynomial.  Conway was the first to popularize them, I believe. 
Why are they useful?  I'm not sure I believe they are so useful.  Sometimes I'm interested in computing Alexander invariants but the knots and links that I'm looking at do not have easy-to-compute diagrams associated to them.  Say you have a homology 3-sphere and you apply the JSJ-decomposition to it.  This produces some knots and links in homology spheres but working out diagrams can be a pain.  So sometimes it's far easier to use the covering space definition to get at the Alexander polynomials.  Moreover, Skein relations don't give you the Alexander module and how Poincare duality works on the module, or naturality (when you have maps between 3-manifolds), etc. 
A: Conway was the person who gave us the concept of a skein relation (although, in retrospect, a skein relation does appear in the original paper of Alexander on the Alexander polynomial). What we are discussing here are linear skein relations (Conway considered also non-linear skein relations, although he never published on the subject, and the idea seems to have been virtually forgotten). Conway's idea, as I luckily overheard him explain it to Cameron Gordon, was to consider knot invariants not as maps of the set of knots to the set of polynomials (for instance), but as maps from some sort of space of knots, locally characterized by how they behave on knots in "close proximity". What does it mean for two knots to be close to each other? For Conway it meant that they differ by some simple local tangle replacement. That is the skein.
As was mentioned in other answers, this dovetails nicely with later ideas of TQFT and  quantum knot invariants, one of whose defining properties is that they are determined locally on small pieces of the knot or 3-manifold, which are then glued together. It's frightening just how close Conway was to discovering the Jones polynomial using his approach- we can only dream how that might have changed the history of knot theory.
I agree with all the other answers, therefore, that the motivation for skein relations is philosophical rather than as a tool to calculate, for which it is notoriously ill-suited.
A: In the case of the Jones Polynomial, the R matrix that comes from the bracket relation really is a matrix. Consequently, it satisfies a polynomial equation. That polynomial equation can be thought of as a skein relation. This approach was described in a paper by Turaev --- I think in Inventiones.
A: NB: I am not an expert in Heegaard Floer homology.  See this article of Peter Ozsvath for a survey.
The skein relation is the "Euler characteristic" of the exact triangle for Heegaard Floer homology.  That is: Heegaard Floer homology is a bigraded theory.  Let $r_{i,j}$ be the rank of the $ij$th group.  Then the Alexander polynomial is the sum $\sum (-1)^j r_{i,j} T^i$.  
Now, the Heegaard Floer homology groups satisfy an exact triangle.  That is, if $Y_0$, $Y_1$, $Y_\infty$ are the $0, 1, \infty$ surgeries on a three-manifold along a fixed knot then the resulting HF groups fit into a long exact sequence (with a degree shift that I don't understand).  Taking the Euler characteristic of everything in sight and applying the above paragraph gives the skein relation...
For more details we'll have to ask an expert. In particular, why do exact triangles show up in Floer-type homology theories?  And how did Floer discover/invent them?  (This is probably an easier question than asking how Alexander discovered/invented the skein relation?!) 
A: Here is a sketch of how the skein relations appear in the approach to knot invariants based on braided monoidal categories coming e.g. from representations of quantum groups. 
Suppose $V$ is a dualizable object in a braided monoidal category $(C, \otimes)$. This means, among other things, that $V^{\otimes n}$ acquires an action of the braid group $B_n$, and moreover we can meaningfully take traces of the action of a braid in a way which produces an invariant of the knot obtained by closing the braid up. Famously, the Jones polynomial arises in this way when $C$ is taken to be the braided monoidal category of representations of the quantum group $U_q(\mathfrak{sl}_2)$ and $V$ is taken to be the standard $2$-dimensional representation. 
Now, one way to describe the skein relation satisfied by the Jones polynomial is that it is a linear relation between three endomorphisms of $V^{\otimes 2}$, namely


*

*two parallel strands, describing the identity,

*a crossing, describing the braiding $b_{V, V} : V^{\otimes 2} \to V^{\otimes 2}$, and

*the other crossing, describing the inverse $b_{V, V}^{-1}$.  


Now, why might there be a linear relation between these three elements? Certainly a sufficient condition is if $\text{End}(V^{\otimes 2})$ is at most $2$-dimensional. And this actually happens in the Jones polynomial case. (The point is that the representation theory of $U_q(\mathfrak{sl}_2)$ is sufficiently similar to that of $\mathfrak{sl}_2$ that it remains true that $V^{\otimes 2}$ is a direct sum of two nonisomorphic irreducibles.) 
A: Alexander realized they were useful, then Conway.  However, Jones clearly was the one
who really made a big bang with a skein relation. This allowed him to see a connection between the Jones polynomial and state sums in statistical mechanics. This was followed by HOMFLYPT, which might be the first time a skein relation was used to define an invariant rather than encapsulate some of its properties.  I would say that Kauffman really simplified the study of the Jones polynomial by way of his bracket relation.  Witten used the skein relation to build a hypothetical connection with TQFT. This connection was made rigorous by Reshitkhin and Turaev from a quantum groups perspective. The work of Habeger, Masbaum, Vogel, and Blanchet made it rigorous from a skein theoretic viewpoint. The connection between skein relations and Lie groups probably appeared first in the work of Turaev and Wenzl, where they classified skein relations by what family of Lie groups you were working with. There was work of Blanchet and Beliakova that built on this, especially understanding B-type Lie algebras. Xiao-Song Lin built a connection between the Jones polynomial and finite type invariants with skein relations. Effie Kalfagianni used them to extend the Jones polynomial to knots in other three-manifolds. Bar-Natan used skein relations to powerful effect to build connections between finite type invariants and Lie algebras.  Bullock's work was the first to build the direct connection between skein relations and trace identities. This was built on in the work of Sikora who did it for many more Lie groups.  Kuperberg's spiders were also actually about skein relations, and his work is starting have impact in the study of flag varieties.  The skein relation short exact sequence of chain complexes first appeared in the work of Khovanov, though it had been simmering in Floer theory for a long time in the related surgery triangle.
I thought I would give a motivating example.
Recall that matrices satisfy their characteristic polynomial.  If $A$ is a two by two matrix of determinant one, then its characteristic polynomial is $\lambda^2-tr(A)\lambda +1$. Hence we know $A^2-(tr(A)A+Id=0$ where the zero on the right is a two by two matrix of zeroes.
Multiply this through by $A^{-1}$ to symmetrize it as $A+tr(A)Id +A^{-1}=0$.  Now multiply by any two by two matrix $B$ to get $BA-tr(A)B+BA^{-1}=0$.  Finally, take the trace to get
$tr(BA)-tr(A)tr(B)+tr(BA^{-1})=0$.  This is the fundamental trace identity for $SL_2(\mathbb{C})$. Let $X_i$ be variables which you can think of as $2\times 2$ matrices.
Form all words in the $X_i$ and then take all polynomials in traces of these words.  Every identity between these polynomials is a consequence of $tr(A)=tr(A^{-1})$, $tr(AB)=tr(BA)$,
$tr(Id)=2$,
and the fundamental trace identity.
Let $M$ be  a topological space.  Take polynomials on free homotopy classes of loops in $M$ and mod out by the relations coming from replacing a loop by its inverse, replacing the null homotopic loop by $-2$, and the Kauffman bracket skein relaton with $A$ set equal to $-1$.  In this setting the Kauffman bracket skein relation is the fundamental trace identity.
This ring is the coordinate ring of the unreduced affine scheme of characters of $SL_2(\mathbb{C})$ representations of the fundamental group of $M$.  
If $M$ is a surface then you can fatten the surface up to $M\times [0,1]$ and instead use framed links in $M\times [0,1]$. You multiply by stacking framed links. Use the Kauffman bracket skein relations at $A=e^h$.  This algebra is a quantization of the $SL_2(\mathbb{C})$ representations of the fundamental group of the surface with respect to Goldman's Poisson structure.  That fact is established by proving that Goldman's Poisson bracket can be computed skein theoretically.
A good starting point for the above material might be the article "Understanding the Kauffman Bracket Skein Relation" by Bullock, F, and Kania-Bartoszynska.
The importance of skein relations is that it allows you to make teleological connections between knot polynomials and other, seemingly distant areas of mathematics like representation theory, quantization, algebraic geometry,  gauge theory, and low dimensional geometry and topology.
A: Why they are useful is related to one reason Polynomial invariants are useful themselves: they let you prove theorems, when they acutally do let you prove theorems.  In particular, if you have a gadget determined by a link-diagram, AND you know that it satisfies a skein relation, THEN that information may be enough to prove that your gadget is isotopy-invariant, because if you're lucky, you can relate the Reidemeister moves to a very few skein-relation applications.  Of course, this may not always be the case, but it's handy when it is.
A: Perhaps this is a better answer the question in your title and might be "a" motivation and "the" motivation, but the +. -, 0 Skein triple also is related to a biological process involving DNA. Basically, there are enzymes Topoisomerase and Recombinase that together preform a crossing change on knotted DNA just like in the Skein triple. Although this was discovered well after the creation of the Skein triple, it might be worth mentioning (the next time you teach your class). A good reference for Topoisomerase, Recombinase, and the Skein triple is Eanst and Sumners A calculus for rational tangles: applications to DNA recombination, however there is also a mention of this process in Colin Adams' Knot book.  
As other people have posted, there is a lot of really interesting math surrounding Skein triples. What might be even more surprising given the work of Ernst, Sumners, and those that followed them, there is really interesting applied math surrounding Skein triples! 
A: One of the earliest appearances of the ingredients for a skein relation can be found in Romilly Allen's 1904 book on Celtic Knotting. There he explains that designers of Celtic knot patterns first start with a regular weave and then systematically replace some of the crossings by "horizontal" and "vertical" smoothings. These days, it is easy to find working demonstrations of this process on the internet. The skein triple consists in an unoriented crossing and its two possible smoothings. This is the skein triple underlying the bracket polynomial model for the Jones polynomial and directly related to Temperley-Lieb algebra. Of course neither Romilly Allen nor the Celtic knotters had any intention to calculate polynomial invariants of knots! That came much later. Another important point about this simplest skein relation is that it is related (by shading the link diagram) to the contraction and deletion operations on the edges of a plane graph. This is why the bracket polynomial and the Jones polynomial are related to the Dichromatic (Tutte) polynomial and to signed generalizations of the Tutte polynomial. And then finally, the two smoothings of a crossing are related to one another in that they form the 'top' and 'bottom' of a saddle surface that joins them. This is the key geometric idea behind Khovanov homology.
