"Naturality" in a categorical sense is much more than "not depending on choices", and, also, is essentially unrelated to issues about the Axiom of Choice.
In the example of vector spaces over a field, we can look at the category of _finite_dimensional_ vector spaces, to avoid worrying about using AxCh to find elements of the dual. The non naturality of any isomorphisms of finite-dimensional vectorspaces with their duals resides in the fact that, provably, as a not-hard exercise, there is no collection of isomorphisms $\phi_V:V\rightarrow V^*$ of isomorphisms of f.d. v.s.'s $V$ to their duals, compatible with all v.s. homs $f:V\rightarrow W$.
In contrast, the isomorphism $\phi_V:V\rightarrow V^{**}$ to the second dual, by $\phi_V(v)(\lambda)=\lambda(v)$ is compatible with all homs, as an easy exericise! This latter compatibility is the serious meaning of "naturality".
True, if capricious or random choices play a role, the chance that the outcome is natural in this sense is certainly diminished! But that aspect is not the defining property!
Edit (16 Apr '12): as alancalvitti notes, the ubiquity of adjunctions, and the naturality and sense of "naturality", and counter-examples to naive portrayals, deserve wider treatment at introductory levels. After all, this can be done with almost no serious "formal" category-theoretic overhead, and pays wonderful returns, at the very least organizing one's thinking. Distinguishing "characterization" from "construction-to-prove-existence" is related. E.g., "Why is the product topology so coarse?": to say that "it's the definition" is unhelpful; to take the categorical definition of "product" and _find_out_ what topology on the cartesian product of sets is the categorical product topology is a do-able, interesting exercise! :)
Just use the naturality relation and the fact that $\alpha^{-1}=\beta.$ That is,
$\alpha_{C'}\circ Fh\circ \beta_C=Gh\circ\alpha_C\circ\beta_C=Gh\circ1_C=Gh\Rightarrow Fh\circ \beta_C=\beta_{C'}\circ Gh$
Best Answer
Formally, the meaning of 'does not depend on particular choices (e.g., of basis)' means precisely that the functions (or morphisms more generally) form a natural transformation. In the original article where Eilenberg and Mac Lane introduce categories they explicitly say that categories are introduced to define functors and that functors are introduced to define natural transformations.
It is very common in mathematics to use the term 'natural' about a construction (long before natural transformations existed) and in pretty much all of those cases it means that one actually constructs a natural transformation in the formal sense of category theory.
Now to answer your questions. A construction in linear algebra is said to be independent of the choice of basis if the construction uses a basis in the definition but choosing any other basis will yield the same final result. For instance, one can define the determinant of a linear transformation $T:V\to V$, on some finite dimensional vector space $V$, to be the determinant of a representing matrix relative to a basis $B$. One can then show that no matter which basis is chosen the determinant of the representing matrix is always the same. Thus, this concept is independent of the choice of basis.
Incidentally, the determinant gives an example of a natural transformation, see Why determinant is a natural transformation?
Now for question 2, quite often when you are able to construct a linear transformation that does not depend on any particular choice of basis it will be the case that this will actually be a general construction that will give you a whole family of linear transformation that together will form a natural transformation.
You might want to have a look at What is a natural isomorphism? for more examples.