The
Well Ordering Theorem says that every
set may be
well ordered (which see for yet more discussion in excruciating detail);
not the same as defining a
total order on the set.
This requires the axiom of choice even for "trivial" sets. For the natural numbers the standard ordering is a well ordering (every set of positive integers has a smallest element!), and the axiom of choice isn't needed. So you don't need Choice for any other countable set, either -- just use a bijection between your set and the natural numbers, defining the ordering in the natural numbers.
Ordering of ordinal numbers is a well ordering, so if you have an ordinal number with the same cardinality as your set you have a well ordering for your set. The theorem says you can always find such an ordinal number.
The unpleasant situation is with the set of real numbers, say. We don't even know the cardinality of the set (see the continuum hypothesis!). What would a well ordering of the real numbers look like?
We're looking for an order relation "<<" for which every set of real numbers has a least element. Obviously our beloved "<" relation fails miserably (it even fails for rational numbers): the set {1/n}n=0oo clearly has no least element. It's not clear how to define a well-ordering here; indeed, the dependence on the Axiom of Choice shows that it's impossible to construct such an ordering.