As Thorny said, Milnor's axiomatic definition seems to be precisely the best way of proving that different definitions are the same. The main thrust of his "definition" is the proof that any invariants that satisfy these axioms must be the same as Stiefel-Whitney classes. In his book, they connect the two notions I describe below as well as the Steenrod-squares definition. They should also serve to prove that all the definitions you talk about are the same.
The rest of this answer might have less to do with your exact question than with my tendency to see an interesting question title and start writing. Sorry! Still, I feel that they are things that should be said (or, at least, don't deserve to be deleted).
I think there are two very important ways to understand characteristic classes. Both are explained in Milnor's Characteristic Classes, but not as the definition, since they are not as precise (but, to me, they are much more intuitive).
Think of your vector bundle as a map from your space X into a Grassmanian. The cohomology of the Grassmanian (more precisely, either the $\mathbb Z/2$ cohomology of the real Grassmanian, or the usual cohomology of the complex Grassmanian) is a polynomial algebra on some generators. The characteristic classes (Stiefel-Whitney or Chern, respectively) are precisely the pullbacks of these cohomology classes to X via the map.
Reading your question carefully, I guess you already knew this. Still, I think you should give this definition more credit. In particular, I think that this is the best explanation of the philosophical reason why "characteristic classes" exist. On thing that confuses me: why are the pullbacks of the integer cohomology of the real Grassmanian never called characteristic classes? I'm sure they are a pain to calculate, but that doesn't justify why nobody seems to care for them at all...
You can understand them through obstruction theory (another reference: Steenrod's "Theory of Fibre Bundles). The idea is to generalize the definition of the Euler characteristic using vector fields. Namely, try to construct a nowhere-zero section of your bundle. The obstruction will be a cohomology class, which is called the Euler class (and corresponds mod 2 to the top Stiefel-Whitney class). Try to construct two linearly independent nowhere-zero sections of the bundle. The obstruction will be a cohomology class which, mod 2, will be the next (one dimension lower) Stiefel-Whitney class. If you keep going like this, you'll construct all the classes.
Here is an explanation of why the obstructions to constructing non-zero sections are cohomology classes, for the case of a single section.
Think of your space X as a CW-complex; start constructing it on the 0-skeleton, and then try extending the section to 1-skeleton, and so on. At each step, you will basically be solving the following problem:
Given a vector field on the boundary $S^{n-1}$ or the ball $B^n$, can you extend it to the whole ball?
To solve this, think of the vector field as a map $S^{n-1}\to \mathbb R^m$ where m is the dimension of your bundle (you can assume that the bundle is trivial over the ball $B^n$ since the ball is contractible). Since the vector field is supposed to be nowhere zero, you can think of this as a map $S^{n-1}\to S^{m-1}$. If $n<m$, this map is always nullhomotopic and always extends to the ball. If $n=m$, you get an integer, the degree of the map, which tells you if you can extend. Since you get an integer for each degree-m cell of the CW-complex, you get something that looks like a cohomology class in $H^m(X)$ (of course, you need to verify separately that it actually is one, and if you are precise enough, you'll see that these integers only make sense mod 2). This is the Euler class.
If you wanted to construct two linearly independent sections, first construct one up to the $n-1$-skeleton (which is always possible). Now, let's start making the second one. You might as well require the second section to be orthogonal to the first. So, in the extension problem, you'll have a map $S^{n-1}\to \mathbb R^{m-1}$ where the $\mathbb R^{m-1} \subset \mathbb R^m$ is the subspace orthogonal to the first section. Since it also can't be zero, it's really a map $S^{n-1}\to S^{m-2}$. The rest of the argument is the same; you get a class in $H^{m-1}(X)$.
Usual disclaimer: there may be mistakes anywhere. Please point them out!