A few days ago I was recalling some facts about the p-adic numbers, for example the fact that the p-adic metric is an ultrametric implies very strongly that there is no order on $\mathbb{Q}_p$, as any number in the interior of an open ball is in fact its center.
This argument is not correct. For instance why does it not apply to $\mathbb{Q}$ with the $p$-adic metric? In fact any field which admits an ordering also admits a nontrivial non-Archimedean metric.
It is true though that $\mathbb{Q}_p$ cannot be ordered. By the Artin-Schreier theorem, this is equivalent to the fact that $-1$ is a sum of squares. Using Hensel's Lemma and a little quadratic form theory it is not hard to show that $-1$ is a sum of four squares in $\mathbb{Q}_p$.
I know that if you take the completion of the algebraic close of the p-adic completion you get something which is isomorphic to $\mathbb{C}$ (this result was very surprising until I studied model theory, then it became obvious).
I don't mean to pick, but I am familiar with basic model theory and I don't see how it helps to establish this result. Rather it is basic field theory: any two algebraically closed fields of equal characteristic and absolute transcendence degree are isomorphic. (From this the completeness of the theory of algebraically closed fields of any given characteristic follows easily, by Vaught's test.)
So I was thinking, is there a $p$-adic number whose square equals 2? 3? 2011? For which prime numbers $p$?
All of these answers depend on $p$. The general situation is as follows: for any odd $p$, the group of square classes $\mathbb{Q}_p^{\times}/\mathbb{Q}_p^{\times 2}$ -- which parameterizes quadratic extensions -- has order $4$, meaning there are exactly three quadratic extensions of $\mathbb{Q}_p$ inside any algebraic closure. If $u$ is any integer which is not a square modulo $p$, then these three extensions are given by adjoinging $\sqrt{p}$, $\sqrt{u}$ and $\sqrt{up}$. When $p = 2$ the group of square classes has cardinality $8$, meaning there are $7$ quadratic extensions.
How far down the rabbit hole of algebraic numbers can you go inside the p-adic numbers? Are there general results connecting the choice (or rather properties) of $p$ to the "amount" of algebraic closure it gives?
I don't know exactly what you are looking for as an answer here. The absolute Galois group of $\mathbb{Q}_p$ is in some sense rather well understood: it is an infinite profinite group but it is "small" in the technical sense that there are only finitely many open subgroups of any given index. Also every finite extension of $\mathbb{Q}_p$ is solvable. All in all it is vague -- but fair -- to say that the fields $\mathbb{Q}_p$ are "much closer to being algebraically closed" than the field $\mathbb{Q}$ but "not as close to being algebraically closed" as the finite field $\mathbb{F}_p$. This can be made precise in various ways.
If you are interested in the $p$-adic numbers you should read intermediate level number theory texts on local fields. For instance this page collects notes from a course on (in part) local fields that I taught last spring. I also highly recommend books called Local Fields: one by Cassels and one by Serre.
Added: see in particular Sections 5.4 and 5.5 of this set of notes for information about the number of $n$th power classes and the number of field extensions of a given degree.
For any finite or countable field $K$, you can well-order $K$ even without AC, and then you don't actually need any further choice to construct a closure for it.
Namely, since $K$ can be well-ordered, you can well-order all monic polynomials over $K$ and adjoin roots for the irreducible ones one by one by transfinite induction up to $\omega_1$. Each time we adjoin elements, we can well-order the new elements and stick them at the end of the well-ordering of the ones we already have. If we order the polynomials primarily by "maximal coefficient" rather than by degree, the new polynomials that become possible after each extension will always come after the ones we already know.
By the time we reach $\omega_1$, there cannot be any more polynomials that need to have roots adjoined. Namely, every polynomial we can form at that point will have had each of its coefficients added at a time when there were only countably many polynomials in our list of polynomials to process, so this polynomial will have been processed at some step before $\omega_1$.
Edit to add: In fact, as Zhen Lin points out, one only has to adjoin roots for polynomials with coefficients in $K$. For $K=\mathbb Q$ that is shown in this question, but the arguments there appear to work in general. This is easy enough to do for any well-orderable $K$, not just countable ones.
Best Answer
The typical construction of $\mathbb{C}_p$ goes through the following steps:
You are probably worried about the first step, but there's actually also a subtle issue in the third step, which is that the standard definition of the completion of a metric space (i.e., the collection of Cauchy sequences modulo distance $0$) isn't actually 'correct' in situations with very little choice. Specifically, there can be metric spaces $X$ and $Y$ with $X$ dense in $Y$ such that not every element of $Y$ is the limit of a sequence of elements of $X$. So with that in mind, we'll say that a metric space $X$ is complete if the image of any isometric embedding of $X$ into another metric space is closed. $\mathsf{ZF}$ proves that every metric spaces has a unique completion in the typical sense. (There is a way to explicitly construct this completion in terms of 'Cauchy filters' instead of Cauchy sequences.)
To actually answer your question, $\mathsf{ZF}$ does prove that for each prime $p$, there is a valued field $\mathbb{C}_p$ extending $\mathbb{Q}_p$ with the properties that
(I don't know whether we can prove that this $\mathbb{C}_p$ is unique in any way.)
Here is a sketch of a terrible proof of this:
Fix a model $V$ of $\mathsf{ZF}$. Let $\mathbb{Q}_p^V$ be $V$'s copy of the $p$-adic numbers. Every model of $\mathsf{ZF}$ has an inner model $L$ of $\mathsf{ZFC}$. Let $\mathbb{Q}_p^L$ be $L$'s copy of the $p$-adic numbers. Since the integers are dense in $\mathbb{Q}_p$, there is a canonical way of thinking of $\mathbb{Q}_p^L$ as a sub-field of $\mathbb{Q}_p^V$. Perform the normal algebraic closure argument inside $L$ to get $\overline{\mathbb{Q}}_p^L$. Let $\mathbb{C}_p^V$ be the metric completion of $\overline{\mathbb{Q}}_p^L$ computed in $V$. Argue that $\mathbb{C}_p^V$ has the required properties: Note that $\mathbb{Q}_p^V$ can be identified with a certain subset of $\mathbb{C}_p^V$. Let $F$ be a proper sub-field of $\mathbb{C}_p^V$ containing $\mathbb{Q}_p^V$ (and therefore also $\mathbb{Q}_p^L$). If $F$ is dense in $\mathbb{C}_p^V$, then $F$ is not metrically complete. If $F$ is not dense in $\mathbb{C}_p^V$, then there is an element $a$ of $\overline{\mathbb{Q}}_p^L$ and a rational $\varepsilon >0$ such that the ball $B_{\leq \varepsilon}(a)$ is disjoint from $F$, but this implies that $F$ is not algebraically closed. Finally we need to check that $\mathbb{C}_p^V$ is algebraically closed. This follows from Hensel's lemma and approximating elements of $\mathbb{Q}_p^V$ with elements of $\mathbb{Q}_p^L$. (Technically we also need to check that $\mathbb{C}_p^V$ has a sensible field structure extending $\overline{\mathbb{Q}}_p^L$, but this is pretty easy.) $\square$
A more honest proof of this would be to build the algebraic closure of some countable dense sub-field of $\mathbb{Q}_p$, such as just the rationals, and then extend the valuation and take the metric completion.
A more difficult question is whether you can always form a spherically complete, algebraically closed field extension of $\mathbb{Q}_p$, since such fields (sometimes denoted $\Omega_p$) are usually constructed using an ultraproduct.