Answer by Edwin Chen:
I like to use Bertrand Russell's explanation: "The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes."
Let's see what this means. Suppose you have an infinite set of drawers, each containing a pair of shoes, and you want your robot to pick a shoe from each drawer and check if it's clean. Your robot isn't very advanced, so you need to give it very precise instructions on which shoe to pick. What do you tell your robot? One possibility is to tell it to always pick the shoe for the left foot.
But suppose each drawer also contains an identical pair of socks. How can you tell your robot to pick a sock from each? You can't tell it to pick the left-foot sock (socks look the same, unlike shoes), you can't tell it to pick the bigger sock (they're the same size), you can't tell it to flip a coin and pick the sock on the left if the coin lands heads (your robot doesn't have any random number generation properties), and let's suppose for the purpose of this analogy that you can't tell it to pick the sock on the left or on the top. If there were only a finite set of drawers, there wouldn't be any problem: you could simply go to the first drawer, hold up a sock and mark it with a pen, and tell your robot to pick this one. But with an infinite set of drawers, you can't do this, since it would take infinite time to go through each drawer and mark a sock. Assuming the Axiom of Choice, however, basically grants your robot the power to impose an arbitrary order on each pair of socks and pick one itself.
Translating this into the formal definition of the Axiom of Choice: for any collection X of nonempty sets (for any collection X of drawers each containing at least one shoe/sock), there exists a choice function f (there exists a way for your simple robot to pick a shoe/sock from each drawer) defined on X.
The reason the Axiom of Choice is (somewhat) controversial is that while it allows us to prove some very useful mathematical statements (we can now check whether each drawer contains a clean sock or not!), it also allows us to prove some less intuitive statements (e.g., the Banach-Tarski paradox).
Also, just for kicks, here's a slightly different way of thinking about choice functions: Suppose I give you a robot Jim who has enough free will to choose from two-element sets (e.g., if you give him two chinchillas, he can say which one is cuter), but three-element sets and four-element sets confound him. Can you use Jim to build another robot with enough free will to perform these last two judging tasks (given three or four chinchillas, pick one as the cutest)?