http://en.m.wikipedia.org/wiki/Dimension_theorem#section_1
Let's first not assume any choice principle.
Let $V$ be a vector space over a field $F$ and $\beta_1,\beta_2$ be bases for $V$.
Suppose $\beta_1\succ \beta_2$.
Let $I$ and $J$ be indexing sets for $\beta_1,\beta_2$ respectively, so that $\beta_1=\{u_i:i\in I\}$ and $\beta_2=\{v_j:j\in J\}$
For each $j\in J$, let $E_j$ be the unique finite subset of $I$ and $C_j\triangleq \{a_{j_i}\}_{i\in E_j}$ be the unique subset of $F$ such that $v_j=\sum_{i\in E_j} a_{j_i} u_{j_i}$ and $\forall i\in E_j, a_{j_i}≠0$.
(Since unique representation theorem can be proved in ZF, choice is not used till now.)
Thus, $\{(E_j,C_j)\}_{j\in J}$ is a family of distinct sets so that $\{(E_j,C_j)\}_{j\in J}\approx J$.
Now, I want to claim that $\bigcup_{j\in J} E_j \prec I$. I see choice is in need here, but why ultrafilter lemma?
Moreover, does ultrafilter lemma imply that every set is comparable? (You don't need to explain this to me, I just want to know if it is or not..:))
A sketch of the proof that all bases have the same cardinality, assuming only ZF + the Boolean prime ideal theorem (which is equivalent to ZF + the ultrafilter lemma, and is strictly weaker than ZFC) is given here: https://mathoverflow.net/questions/93242/sizes-of-bases-of-vector-spaces-without-the-axiom-of-choice/93359#93359. The proof is not at all obvious from what it says on the Wikipedia page.
I should mention that if you do not want to use full AC, then you should not start by saying "suppose $\beta_1 \succ \beta_2$" or even "suppose $\beta_1 \succeq \beta_2$". The goal of the proof is to construct injections between the bases.