First read the writeup on symmetric polynomials to see the statement of The Fundamental Theorem. Before we start the proof it's worth noting that it is constructive, in the sense that it actually gives an algorithm that you can carry out in any particular case.

Proof: Let f(x1,...,xn) be a symmetric polynomial. We have to express it in terms on the elementary symmetric polynomials s1,...,sn. Well our polynomial f is a sum of monomials, that is terms of the form a(x1)i1....(xn)in where a is a nonzero scalar (from our field) and (i1,...,in) are all natural numbers.

First of all we have to locate the biggest monomial. To do this we use the lexicographic ordering on n-tuples of natural numbers. If we have two monomials p=ax1i1....axnin and q=bx1j1....xnjn then we say that p < q iff (i1,...,in) < (i1,...,in).

Suppose then that p is the largest monomial in f with respect to this order. Since f is symmetric we must have that s(p)=axs(1)i1....xs(n)in is also a monomial of f for any permutation s in the symmetric group. Because we chose p to be the largest we can see from this that we must have that i1 >= i2 >=...>= in.

Next we want to find a first approximation to f made from symmetric polynomials. So let g=as1i1-i2s2i2-i3....snin. Now considering all the monomials that occur in g we can see that one of these monomials is ax1i1-i2(x1x2)i2-i3...(x1...xn)in which is exactly equal to the largest monomial of f. Now consider the polynomial f-g, it is symmetric and its largest monomial is smaller than the largest monomial of f. So we are done by induction.