This is a response to Joel's comment about whether $2^{\mathbb R}$ can be linearly ordered without choice. In general, no. There is a concrete obstacle, actually: Vitali's equivalence relation. Recall that this relation is defined by $x\sim y$ iff $x-y\in{\mathbb Q}$. Now consider ${\mathbb R}/\sim$, the collection of equivalence classes. This is a concrete subset of $2^{\mathbb R}$ that in general cannot be linearly ordered without some appeal to choice.
For example, under determinacy, this set is not linearly orderable, so in $L({\mathbb R})$ there is no linear ordering of it in the presence of large cardinals. In short, under reasonable assumptions, there is no way of linearly order this set without appealing to choice.
Things get interesting. For example, in $L({\mathbb R})$ (the smallest model of ZF that contains all the reals), in the presence of large cardinals, a set is linearly orderable iff ${\mathbb R}/\sim$ does not inject into it, and a set is well-orderable iff ${\mathbb R}$ does not inject into it.