Do we really need Choice to pick socks? It is said that you need the Axiom of Choice to pick one sock from each of infinitely many pairs, but that you don't need it for shoes, since you can just pick all the left shoes.
But Choice is equivalent to the statement that every set can be well-ordered, right? And can't be well-order a two-element (or any finite) set without invoking anything related to Choice? If so, doesn't that mean we don't need Choice to pick socks after all?
 A: The axiom of choice is not needed to choose from one pair of socks. You do that every morning when you put on your socks. In fact, even if you have infinitely many socks, choosing one doesn't require the axiom of choice. Neither does choosing five, or ten socks. That's just existential instantiation and induction.
The axiom of choice is needed in order to choose from infinitely many pairs at once. The reason is that between two socks, there is no "left" or "right", and there is no distinguishing property that we can always say that "given a pair of socks, one of them is such and such". And so the axiom of choice is really needed for that.
More formally, Fraenkel, and later Cohen, showed that this argument is mathematically solid. It is consistent that the axiom of choice fails, and there is a set which is the countable union of pairs, but there is no function which chooses a single element from each pair.
A: I think Asaf's answer above is generally excellent, but I'll add a few thoughts. I think that this is a place where the metaphors we use to convey mathematics can fail, as there are often several layers of precision that get lost in the metaphor, and become yet more and more clumsy to keep track of. For example: when we say "infinitely many pairs of socks", we do not want to mean "infinitely many copies of the same pair of socks" as in that case, we could have just kept track of where a single sock from the original pair went in each copy (sort of). Instead we want to mean a collection of infinitely many distinct pairs of socks. Now you might object that surely we could just identify all of these together as a single pair. But how exactly? Let's say we have two bins "Sock 1" and "Sock 2". We have to take one of the first pair socks and throw it in "Sock 1" and one of the second pair and ... . You might notice we just used the axiom of choice. 
To make some of the above more precise: suppose we have an infinite index set $I$. Then "infinitely many copies of the same pair" corresponds to the set of functions $$f: I \to \{sock_1,sock_2\}$$
while the axiom of choice metaphor corresponds to takeing a collection of two element sets $A_i$, and then finding a function $$I \to 
\bigcup_{i\in I} A_i$$
Such that $f(i) \in A_i$ for each $i$. This subtle difference is worth meditating on. 
A: You still need axiom of choice to pick a certain order for every pair of socks (this is equivalent to pick a sock for every pair indeed). This does not happen for shoes since shoe pairs come with a predefined order.
A: Yes you do need the axiom of choice to show that for any set of pairs of socks, there is a choice function that picks one sock from each pair. Each sock from one of those pairs can either function as a left sock or as a right sock so that doesn't give us a way to define in terms of each pair of socks in that set of pairs one sock from that pair. The fact that each pair of socks in that set of pairs can be well ordered is not enough to show that there is a function that assigns to each pair of socks one sock in that pair. To show that such a function exists, you have to assume that the union of all pairs of socks in that set of pairs can be well ordered.
Suppose you have a set of infinitely many pairs of socks. If all those socks were instead shoes and any two socks in a pair were instead a left shoe and a right shoe, then a choice function would exist so how could such a function not exist just because they're socks instead of shoes? That's because to show that the set of pairs of socks has a choice function, you have to assume that that set is a set that can be gotten by turning each shoe in the union of a set of pairs of shoes into a sock and that assumption can't be proven without using the axiom of choice.
