This question was motivated by the comments to Dual of Zorn's Lemma?
Let's denote by the Dual Schroeder-Bernstein theorem (DSB) the statement
For any sets $A$ and $B$, if there are surjections from $A$ onto $B$ and from $B$ onto $A$, then there is a bijection between them.
In set theory without choice, assume that the Dual Schroeder-Bernstein theorem holds. Does it follow that choice must hold as well?
I strongly suspect this is open, though I would be glad to be proven wrong in this regard. In all models of ZF without choice that I have examined, DSB fails. This really does not say much, as there are plenty of models I have not looked at. In any case, I don't see how to even formlate an approach to show the consistency of DSB without AC.
The only reference I know for this is Bernhard Banaschewski, Gregory H. Moore, The dual Cantor-Bernstein theorem and the partition principle, Notre Dame J. Formal Logic 31 (3), (1990), 375–381. In this paper it is shown that a strengthening of DSB does imply AC, namely, that whenever there are surjections $f:A\to B$ and $g:B\to A$, then there is a bijection $h:A\to B$ contained in $f\cup g^{-1}$. (Note that the usual Schroeder-Bernstein theorem holds -without needing choice- in this fashion.)
The partition principle is the statement that whenever there is a surjection from $A$ onto $B$, then there is an injection from $B$ into $A$. As far as I know, it is open whether this implies choice, or whether DSB implies the partition principle. Clearly, the reverse implications hold.
If you are interested in natural examples of failures of DSB in some of the usual models, Benjamin Miller wrote a nice note on this, available at his page.
Added Sep. 21. [Edited Aug. 14, 2012] It may be worthwhile to point out what is known, beyond the Banaschewski-Moore result mentioned above.
Assume DSB, and suppose $x$ is equipotent with $x\sqcup x$. Then, if there is a surjection from $x$ onto a set $y$, we also have an injection from $y$ into $x$. (So we have a weak version of the partition principle.) This idemmultiple hypothesis that $x\sqcup x$ is equipotent to $x$, for all infinite sets $x$, is strictly weaker than choice, as shown in Gershon Sageev, An independence result concerning the axiom of choice, Ann. Math. Logic 8 (1975), 1–184, MR0366668 (51 #2915).
Also, as indicated in Arturo Magidin's answer (and the links in the comments), H. Rubin proved that DSB implies that any infinite set contains a countable subset.
Best Answer
This is only a partial answer because I'm having trouble reconstructing something I think I figured out seven years ago...
It would seem the Dual Cantor-Bernstein implies Countable Choice. In a post in sci.math in March 2003 discussing the dual of Cantor-Bernstein, Herman Rubin essentially points out that if the dual of Cantor-Bernstein holds, then every infinite set has a denumerable subset; this is equivalent, I believe, to Countable Choice.
Let $U$ be an infinite set. Let $A$ be the set of all $n$-tuples of elements of $U$ with $n\gt 0$ and even, and let $B$ be the set of all $n$-tuples of $U$ with $n$ odd. There are surjections from $A$ onto $B$ (delete the first element of the tuple) and from $B$ onto $A$ (for the $1$-tuples, map to a fixed element of $A$; for the rest, delete the first element of the tuple). If we assume the dual of Cantor-Bernstein holds, then there exists a one-to-one function from $f\colon B\to A$ (in fact, a bijection). Rubin writes that "a 1-1 mapping from $B$ to $A$ quickly gives a countable subset of $U$", but right now I'm not quite seeing it...