Completion of ZFC
I am not sure which statement you heard as the "Ultimate $L$ axiom," but I will assume it is the following version:
There is a proper class of Woodin cardinals, and for all sentences $\varphi$ that hold in $V$, there is a universally Baire set $A\subseteq{\mathbb R}$ such that, letting $\theta=\Theta^{L(A,{\mathbb R})}$, we have that $HOD^{L(A,{\mathbb R})}\cap V_\theta\models\varphi$.
(At least, this is the version of the axiom that was stated during Woodin's plenary talk at the 2010 ICM, which should be accessible from this link. See also the slides for this talk--Thanks to John Stillwell for the link.)
I do not think you will find much about it in the current literature, but Woodin has written a long manuscript ("Suitable extender models") that should probably provide us with the standard reference once it is published.
As stated, this is really an infinite list of axioms (one for each $\varphi$). The statement is very technical, and it may be a bit difficult to see what its connection is with Woodin's program of searching for nice inner models for supercompactness. (That was the topic of his recent series of talks at Luminy; I wrote notes on them and they can be found here.)
Keeping the discussion at an informal level (which makes what follows not entirely correct), what is going on is the following:
Gödel defined $L$, the constructible universe. It is an inner model of set theory, and it can be analyzed in great detail. In a sense (guided by specific technical results), we feel there is only one model $L$, although of course by the incompleteness theorems we cannot expect to prove all its properties within any particular formal framework. Think of the natural numbers for an analogue: Although no formal theory can prove all their properties, most mathematicians would agree that there is only one "true" set of natural numbers (up to isomorphism). This "completeness" of $L$ is a very desirable feature of a model, but we feel $L$ is too far from the actual universe of sets, in that no significant large cardinals can belong to it.
The inner model program attempts to build $L$-like models that allow the presence of large cardinals and therefore are closer to what we could think of as the "true universe of sets"; again, the goal is to build certain canonical inner models that are unique in a sense (similar to the uniqueness of ${\mathbb N}$ or of $L$), and that (if there are "traces" of large cardinals in the universe $V$) contain large cardinals.
The program has been very successful, but progress is slow. One of the key reasons for this slow development is that the models that are obtained very precisely correspond to specific large cardinals, so that, for example, $L[\mu]$, the canonical $L$-like model for one measurable cardinal, does not allow the existence of even two measurable cardinals ($L$ itself does not even allow one).
Currently, the inner model program reaches far beyond a measurable, but far below a supercompact cardinal. Woodin began an approach with the goal of studying the coarse structure of the inner models for supercompactness. This would be the first step towards the construction of the corresponding $L$-like models. (The second step requires the introduction of so-called fine-structural considerations, and it is traditionally significantly more elaborate than the coarse step.)
The results reported in the talks I linked to above indicate that, if the construction of this model is successful, we will actually have built the "ultimate version of $L$", in that the model we would obtain not only accommodates a supercompact cardinal but, in essence, all large cardinals of the universe.
If we succeed in building such a model, then it makes sense to ask how far it is from the actual universe of sets.
A reasonable position (which Woodin seems to be advocating) is that it makes no sense to distinguish between two theories of sets if each one can interpret the other, because then anything that can be accomplished with one can just as well be accomplished with the other, and differences in presentation would just be linguistic rather than mathematical. One could also argue that of two theories, if one interprets the other but not vice versa, then the "richer" one would be preferable. Of course, one would have to argue for reasons why one would consider the richer theory "true" to begin with. This is a multiverse view of set theory (different in details from other multiverse approaches, such as Hamkins's) and rather different from the traditional view of a distinguished true universe.
Our current understanding of set theory gives us great confidence in the large cardinal hierarchy. $\mathsf{ZFC}$ is incomplete, and so is any theory we can describe. However, there seems to be a linear ordering of strengthenings of $\mathsf{ZFC}$, provided by the large cardinal axioms. Moreover, this is not an arbitrary ordering, but in fact most extensions of $\mathsf{ZFC}$ that have been studied are mutually interpretable with an extension of $\mathsf{ZFC}$ by large cardinals (and those for which this is not known are expected to follow the same pattern, our current ignorance being solely a consequence of the present state of the inner model program).
So, for example, we can begin with the $L$-like model for, say, a Woodin cardinal, and obtain from it a model of a certain fragment of determinacy while, beginning with this amount of determinacy, we can proceed to build the inner model for a Woodin cardinal. Semantically, we are explaining how to pass from a model of one theory to a model of the other. But we can also describe the process as establishing the mutual interpretability of both theories. Of course, if we begin with the $L$-like model for two Woodin cardinals, we can still interpret the other theory just as before, but that theory may not be strong enough to recover the model with two Woodin cardinals.
From this point of view, a reasonable "ultimate theory" of the universe of sets would be obtained if we can describe "ultimate $L$" and provide evidence that any extension of $\mathsf{ZFC}$ attainable by the means we can currently foresee would be interpretable from the theory of "ultimate $L$".
The ultimate $L$ list of axioms is designed to accomplish precisely this result.
Part of the point is that we expect $L$-like models to cohere with one another in a certain sense, so we can order them. We, in fact, expect that this order can be traced to the complexity of certain iteration strategies which, ultimately, can be described by sets of reals. Our current understanding suggests that these sets of reals ought to be universally Baire. Finally, we expect that the models of the form $$HOD^{L(A,{\mathbb R})}\cap V_\theta$$ as above, are $L$-like models, and that these are all the models we need to consider. The fact that when $A=\emptyset$ we indeed obtain an $L$-like model in the presence of large cardinals, is a significant result of Steel, and it can be generalized as far as our current techniques allow.
The $\Omega$-conjecture, formulated by Woodin a few years ago, would be ultimately responsible for the $HOD^{L(A,{\mathbb R})}\cap V_\theta$ models being all the $L$-like models we need. (Though I do not quite see that formally the "ultimate $L$" list of axioms supersedes the $\Omega$-conjecture). Also, if there is a nice $L$-like model for a supercompact, then the results mentioned earlier suggest we have coherence for all these Hod-models.
The theory of the universe that "ultimate $L$" provides us with is essentially the theory of a very rich $L$-like model. It will not be a complete theory, by the incompleteness theorems, but any theory $T$ whose consistency we can establish by, say, forcing from large cardinals would be interpretable from it, so "ultimate $L$" is all we need, in a sense, to study $T$. Similarly, only adding large cardinal axioms would give us a stronger theory (but then, this strengthening would be immediately absorbed into the "ultimate $L$" framework).
It is in this sense that Woodin says that the "axiom" would give us a complete picture of the universe of sets. It would also be reasonable to say that this is the "correct" way of going about completing $\mathsf{ZFC}$, since any extension can be interpreted from this one.
[Note I am not advocating for the correctness of Woodin's viewpoint, or saying that it is my own. I feel I do not understand many of the technical issues at the moment to make a strong stance. As others, I am awaiting the release of the "suitable extender models" manuscript. Let me close with the disclaimer that, in case the technical details in what I have mentioned are incorrect, the mistakes are mine.]
Edit: (Jan. 10, 2011) Here is a link to slides of a talk by John Steel. Both Woodin's slides linked to above, and Steel's are for talks at the Workshop on Set Theory and the Philosophy of Mathematics, held at the University of Pennsylvania, Oct. 15-17, 2010. Hugh's talk was on Friday the 15th, John's was on Sunday. John's slides are a very elegant presentation of the motivations and mathematics behind the formulation of Ultimate $L$.
(Jul. 26, 2013) Woodin's paper has appeared, in two parts:
W. Hugh Woodin. Suitable extender models I, J. Math. Log., 10 (1-2), (2010), 101–339. MR2802084 (2012g:03135),
and
W. Hugh Woodin. Suitable extender models II: beyond $\omega$-huge, J. Math. Log., 11 (2), (2011), 115–436. MR2914848.
He is also working on a manuscript covering the beginning of the fine structure theory of these models. I will add a link once it becomes available.
John Steel has a nice set of slides discussing in some detail the multiverse view mentioned above: Gödel's program, CSLI meeting, Stanford, June 1, 2013.
For more on why one may want to accept large cardinals as a standard feature of the universe of sets, see here.
Edit (May 17, 2017): W. Hugh Woodin has written a highly accessible survey describing the current state of knowledge regarding Ultimate $L$. For now, see here (I hope to update more substantially if I find the time):
MR3632568. Woodin, W. Hugh. In search of Ultimate-L. The 19th Midrasha Mathematicae lectures. Bull. Symb. Log. 23 (2017), no. 1, 1–109.
Alex, you ask a lot of questions, and I'm in no position to say much about Ultimate L. I'll just address this initial matter:
And how do we know that there are (infinitely) many different completions of ZFC in the first place? Could it be that there is no way to consistently assign truth-values to all first-order sentences, i.e. that no completion exists?
The existence of these completions of ZFC follows from Lindenbaum's lemma, a standard ingredient of proofs of the completeness theorem for first-order logic, at least assuming ZFC to be consistent. This also speaks to your second question there: it could be that no completion of ZFC exists, but only if ZFC itself is already inconsistent.
Ultimate L does not pick a unique completion of ZFC: Since we still want to have a recursively enumerable system of axioms, the theory generated by these axioms it will be incomplete by Gödel incompleteness.
But I share your view of a vertical direction (large cardinals) and a horizontal component (CH or its negation and various other statements that are independent over ZFC but don't have more consistency strength).
Even though we cannot hope to get a reasonable theory that is actually complete, we can try to go as far as possible in consistency strength by allowing large cardinals (note that since the large cardinal axioms seem to form a linear scale, there seems to be a distinguished direction
to increase the consistency strength of our theory). At the same time, we want to keep control about the structure of sets. Hence, we are looking for a universe that is somehow canonical but still knows all the large cardinals. The canonicity would decide what is going
on in the horizontal direction to a large extend, like $V=L$ does.
The existence of large cardinals would provide strength and decide things decided by large cardinals in the "right" way (for example, projective sets (sets of reals obtained by iterating projection and complementation, starting from Borel sets) should be Lebesgue measurable snce this is implied by large cardinals).