I will assume you are familiar with the definitions of cardinality and the ordering of cardinals, even in the absence of choice. If anything is unclear please let me know, and I will see to elaborate if needed.
Fact I: If $\kappa$ is a cardinal, and $\aleph$ is any $\aleph$-number (i.e. a well-orderable cardinal), if $\kappa\le\aleph$ then $\kappa$ can be well ordered as well.
(This is a very nice exercise, in case you do not see it right away).
Definition: (Hartogs number) For an infinite set $\kappa$ we denote $\aleph(\kappa)$ the least ordinal which cannot be injected into $\kappa$.
When assuming the axiom of choice, $\aleph(\kappa)$ is $|\kappa|^+$ (that is the successor cardinal of $|\kappa|$). we have, if so, that $\aleph(\omega)=\omega_1$.
Without the axiom of choice this gets slightly more complicated, since there are sets which cannot be well ordered. In a way, Hartogs number measures how much of the set can we well order.
Consider, for example, the case of $A$ being an amorphous set (that is, $A$ is infinite, and every $B\subseteq A$ is either finite or $A\setminus B$ is finite). Since $A$ is infinite every finite cardinal can be embedded into it. However $\aleph_0\nleq |A|$, therefore $\aleph(A)=\omega$.
Fact II: For every infinite set $A$, the ordinal $\aleph(A)$ is an initial ordinal, i.e. an $\aleph$ cardinal.
Otherwise there is $f\colon \aleph(A)\to\alpha$ which is a injection, and $g\colon\alpha\to A$ which is an injection. Composition of injective functions is injective, therefore $g\circ f\colon \aleph(A)\to A$ is an injection of $\aleph(A)$ into $A$, which is a contradiction to the definition of $\aleph(A)$.
Lemma: If $\kappa$ is an infinite cardinal and $\aleph_\alpha$ is an $\aleph$-number, and $$\kappa+\aleph_\alpha=\kappa\cdot\aleph_\alpha$$ Then $\kappa\le\aleph_\alpha$ or $\kappa\ge\aleph_\alpha$.
Before proving this lemma, let us consider this useful corollary:
Corollary: If $\kappa+\aleph(\kappa)=\kappa\cdot \aleph(\kappa)$ then $\kappa$ can be well ordered.
Proof: Since $\aleph(\kappa)$ cannot be injected into $\kappa$, in particular we have that $\aleph(\kappa)\nleq\kappa$, therefore $\kappa<\aleph(\kappa)$ and so it can be well ordered.
Proof of Lemma: Let $A$ be of cardinality $\kappa$ and $P$ of cardinality $\aleph_\alpha$, without loss of generality we can assume the two sets are disjoint.
Since $|A\times P|=|A\cup P|$, we can also assume there are two disjoint sets $|A'|=|A|$ and $|P'|=|P|$ such that $A\times P=A'\cup P'$.
Since we divide an infinite set into two parts, at least one of the following is bound to occur:
There exists some $a\in A$ such that $\langle a,p\rangle\in A'$ for every $p\in P$, and then we have that $\kappa\ge\aleph_\alpha$ (by the map $p\mapsto\langle a,p\rangle$).
If there is no $a$ as above, then for every $a\in A$ there is some $p\in P$ such that $\langle a,p\rangle\notin A'$. For every $a\in A$ let $p_a\in P$ be the minimal $p\in P$ such that $\langle a,p\rangle\in P'$, and so the injective function $a\mapsto\langle a,p_a\rangle$ is an injective function of $A$ into $P'$, and therefore $\kappa\le\aleph_\alpha$.
Now the main theorem, proved by Tarski.
Theorem: Suppose for every infinite set $A$ it holds $|A|=|A\times A|$, then every set can be well ordered.
Proof: Let $\kappa$ be an infinite cardinal. Consider $\kappa+\aleph(\kappa)$. Our assumption gives us:
$$\kappa+\aleph(\kappa)=(\kappa+\aleph(\kappa))^2=\kappa^2+2\kappa\cdot \aleph(\kappa)+\aleph(\kappa)^2\ge\kappa\cdot \aleph(\kappa)\ge\kappa+\aleph(\kappa)$$
Where the last $\ge$ sign is due to the function from $\kappa\cup \aleph(\kappa)$:
$$x\mapsto\begin{cases}
\langle x,0\rangle & x\in\kappa,x\neq k\\
\langle t,x\rangle & x\in \aleph(\kappa)\\
\langle k,1\rangle & x=k\end{cases}$$
(For fixed $t,k\in\kappa$ and $t\neq k$. Note that we use the fact $\kappa$ is infinite, therefore it has at least two elements).
By the Corollary we have that $\kappa$ can be well ordered.
Pointed out to me on the MathOverflow post of this question, that there was a request to avoid the ordinals. I did think about it, a little bit.
I do remember that studying this proof originally, as well as the proof that "If $\kappa$ is such that $|A|\le\kappa<|\mathcal P(A)|$, then $|A|=\kappa$" implies choice, offers no immediate intuition as for why does the proof works. The use of Hartogs number looks like a magic trick.
However, since the first time I had studied this proof I have gained more than a bite of intuition with regards to the axiom of choice. It seems that this is a good place to slightly give the intuitive explanation for this proof.
I will start by saying that I do not believe that any proof of this theorem will be both concise and reveal the intuition behind it. So even if I were to think really hard and transform this proof into a choice function sort of proof, I doubt it will be any more revealing in its intuition, which is why I have decided to write the following instead -- it seems more profitable to the reader.
It is a rather well known fact that the axiom of choice is equivalent to the assertion that every set can be well ordered. In the absence of choice there are sets that cannot be well ordered. Hartogs number is a way to measure how much out of the set can be well ordered.
The axiom of choice is equivalent, as well, to the assertions that the cardinalities of any two sets can be compared. This is exactly due to the idea of Hartogs number - if we can compare a cardinal with its Hartogs then it can be well ordered.
So essentially what we try to have is "enough" comparability to deduce the well ordering principle. This is exactly what the tricky lemma gives us.
The idea behind the proof of the lemma is that if we break the multiplication into a sum then we can find a way to compare the sets. We can replace the requirement that the second set is well ordered simply by "has a choice function on its power set" (this, however, is equivalent to saying that the set can be well ordered).
From this the theorem follows, proving that we can compare every infinite set with its Hartogs number, therefore implying the set can be well ordered.
Let $x\in\mathbb{R}$. Define $$S_{\leq x}=S~\cap~(-\infty,x]~~~\mathrm{and}~~~S_{>x}=S~\cap~ (x,+\infty)$$ and define $S_{\leq}=\{$ the set of all $x$ such that $S_{\leq x}$ is uncountable $\}$, and $S_>=\{$ the set of all $x$ such that $S_{>x}$ is uncountable $\}$.
$S_{\leq}$ is a non empty$^{(*)}$ interval that extends to infinity on the right, and is therefore of the form $[a,+\infty)$ or $(a,+\infty)$ for some $a\in\mathbb{R}$ or is equal to the whole of $\mathbb{R}$.
Similarly, $S_>$ is a non empty$^{(*)}$ interval that extends to infinity on the left, and is thus of the form $(-\infty,b]$ or $(-\infty,b)$ for some $b\in\mathbb{R}$ or is equal to the whole of $\mathbb{R}$.
$^{(*)}$ : I have used some form of choice I believe when I say that $S_>$ and $S_{\leq}$ are non empty, because I use the fact that with some form of choice, the countable union of countable sets is still countable. Is it countable choice? Since $$S=\cup_{n\in\mathbb{N}}S_{\leq n}$$ is uncountable, at least one of the $S_{<n}$ must be uncountable, and so for some natural number $n$ you have $n\in S_{<}\neq\emptyset$.
Let's show that $S_>\cap S_{\leq}$ is non empty. If either one of $S_>$ or $S_{\leq}$ is the whole real line, there is no problem. So let's suppose none of them is the whole of $\mathbb{R}$.
Suppose $x\in S_{\leq}$ that is $S_{\leq x}=S~\cap~(-\infty,x]$ is uncountable. Since $$\bigcup_{n\in\mathbb{N}^*}S_{\leq x-\frac{1}{n}}\subset S_{\leq x}=S~\cap~(-\infty,x]\subset \{x\}\cup \bigcup_{n\in\mathbb{N}^*}S_{\leq x-\frac{1}{n}}$$ the already used fact that countable unions of countable sets are countable with some form of choice implies that at least one of the $S_{\leq x -\frac{1}{n}}$ is uncountable, which means that for some $n\in\mathbb{N}^*,~x -\frac{1}{n}\in L$ and thus $S_{\leq}$ is open, that is, $$\mathbf{S_{\leq}=(b,+\infty)}$$ for some real number $b$. Similarly, $$\mathbf{S_{>}=(-\infty,a)}$$ for some real number $a$.
Then $S_>\cap S_{\leq}$ is empty iff $a\leq b$. But this would entail that $$S=S_{\leq a}\cup S_{> a}$$ is countable as the union of two countable sets, since $a \notin (-\infty,a)=S_{\leq}$ means $S_{\leq a}$ is countable, and $a \notin (b,+\infty)=S_{>}$ means $S_{> a}$ countable.
Best Answer
Yes. You need some choice. The assertion "Every infinite set has a countable subset" is more than enough, and we can use even less (although people often go with more and assume axiom of countable choice).
A set is called Dedekind infinite when it has a proper subset with the same cardinality. That is $A$ is Dedekind infinite when there is some $B\subsetneq A$ such that $|A|=|B|$. In ZFC every infinite set is Dedekind infinite.
A set which is infinite but not Dedekind infinite is called infinite Dedekind finite set (commonly abbreviated to iDf or Dedekind finite). That is $A$ is iDf if for every $B\subsetneq A$ we have $|B|<|A|$. It does not mean that you cannot split an iDf into two infinite sets.
For example, take two disjoint iDf sets $A,B$ then $A\cup B$ is also iDf but can be split into $A$ and $B$.
Important classification of Dedekind infinite sets is as follows: $$A\text{ is Dedekind infinite}\iff\aleph_0\le|A|$$ We do not require that $A$ will be well orderable, but we do require it will have a countable subset. In particular this shows how assuming the above gives us that every infinite set can be split into two infinite subsets.
This still not enough to prove that for every infinite $A$ there are $B,C\subseteq A$ such that $|A|=|B|=|C|$ and $B\cap C=\emptyset$. However it was proved that the axiom of choice does not follow from the following fact:
For every infinite cardinal $\mathfrak p$ we have: $\mathfrak p = \mathfrak p+\mathfrak p$. (I am unfamiliar with the proof, announced by Sageev in 1973 and published a couple years later).
This means that you can have that every cardinal can be split into two equinumerous parts without the axiom of choice.
Lastly, $A$ is called amorphous if $A$ cannot be split into two infinite subsets. That is to say, $B\subseteq A$ then either $B$ finite or $A\setminus B$ finite. This is a stronger notion than that of infinite Dedekind finite. This is due to the fact that it may be possible to linearly order an infinite Dedekind finite set, while it is impossible to linearly order an amorphous set.
The proof for this fact is as follow: Suppose $<$ is a linear ordering of $A$, take the cut at $a\in A$ to be $\langle a\!\!\mid =\{b\in A\mid b<a\}$. Clearly $a\mapsto\langle a\!\!\mid$ is a bijection between $A$ and the set of cuts in $<$, therefore the set of cuts is also amorphous. Since every cut is a subset of $A$ it is either finite or co-finite, and every set of cuts is finite or co-finite (with respect to the set of all cuts).
If only finite many cuts are finite, then only finitely many cuts are co-finite, which is a contradiction to the fact there are infinitely many cuts and each is a subset of $A$. The same argument shows that there cannot be only finitely many infinite cuts.
In Cohen's first model showing that ZF is consistent with the negation of AC was given by adding an iDf set of reals, which can be linearly ordered (but not well ordered). In particular in this model every set can be linearly ordered (for a slightly more detailed survey, see my answer here).
A note on consistency strength:
From the assumption that ZF is consistent you have that ZFC is consistent, and by forcing you have that "ZF+There is an iDf set+Every set if linearly orderable" is consistent, and by a different forcing you have that "ZF+Amorphous" is consistent. The last two clearly proving the consistency of ZF (if indeed they are consistent).
However, if we measure the consistency by how much we contradict the axiom of choice... well, in this case just as "axiom of countable choice" is stronger than "Every infinite set is Dedekind infinite" (i.e. the former assertion proves the latter over ZF), we have that:
"There exists an amorphous set" proves "There exists an iDf set", while the opposite is not true, as witnessed by the consistency of "ZF+There exists iDf set+Every set can be linearly ordered", since the last assertion is inconsistent with amorphous sets but still consistent with iDf sets.
And by its definition an iDf set which is not amorphous can be written as the disjoint union of two infinite sets. Therefore assuming that there exists an iDf set, but there are no amorphous sets is enough to ensure that every infinite set splits into two infinite sets. Whether or not this implies any other forms of choice (multiple choice, finite choice, choice from pairs, choice from well orderable sets, choice from a well orderable collection of well ordered sets, etc etc.), I do not know the answer for that. I'd be happy to look into this question, but this may take a few days due to prior engagements I have.
Lastly, two papers which may be interesting to this topic of conversation:
J.K.Truss, Classes of Dedekind Finite Cardinals, Fundamenta Mathematicae 84, 187-208, 1974.
In which seven notions of Dedekind finite cardinals (five in addition to finite sets and the one mentioned in my answer, which is the "canonical type" of infinite Dedekind finite cardinals). The paper is not very technical (I think) and I think that one can understand most of the results given without deep background in forcing or permutation models.
J.K.Truss, The structure of amorphous sets, Annals of Pure and Applied Logic, 73 (1995), 191-233.
This paper deals with amorphous sets, it is longer and more difficult than the previous one.
(
I had to dig quite deep into the internet to find these online, and I cannot recall where I had found both papers.Many, many many thanks to Theo for finding the links.)