Qiaochu, using the link I provided in my answer to this question, you find that this question is still open (or was, as of early 2000, and I haven't heard of any recent results in this direction). (According to the site notation, the existence of algebraic closures is form 69, the ultrafilter theorem is form 14, uniqueness of the algebraic closure (in case they exist) is form 233; these numbers can be found by entering appropriate phrases in the last entry form in the page linked to above.)
It is known that uniqueness implies neither existence nor the ultrafilter theorem.
It is open whether existence implies uniqueness or the ultrafilter theorem, and whether (existence and uniqueness) implies it either.
(Enter 14, 69, 233 in Table 1 in the link above for these implications/non-implications.)
Jech's book on the axiom of choice should provide the proofs of the known implications and references, and the book by Howard-Rubin (besides updates past the publication date of Jech's book) provides references for the known non-implications.