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.
Jyrki showed you a specific example of a cauchy sequence not converging in $\mathbb{Z}$, but there is a wholly more dramatic answer. Let's suppose that $\mathbb{Z}$ was complete. Then, every infinite series $\sum_{n=0}^{\infty}a_np^n$ with $a_n\in\{0,1,\ldots,p-1\}$ would converge.(because each such series has partial sums that are Cauchy). Moreover, two such infinite series are equal if and only if their coefficients (of $p^n$) are equal (just check their valuations). Thus, we'd have an injection $(\mathbb{Z}/p\mathbb{Z})^\mathbb{N}\to \mathbb{Z}$ which is problematic due to carinality issues.
This also shows that $\mathbb{Q}$ is not complete
Best Answer
It’s sufficient to look at balls centred at $0$. It’s easiest to see if you represent the $p$-adic rationals in the form $$x = \sum_{k\ge k_0}x_kp^k,$$ where the $x_k$ are the $p$-adic digits of $x$, so that $$B(0,r) = \left\{\sum_{k\ge r} x_kp^k:\forall k\bigg(x_k\in\{0,1,\dots,p-1\}\bigg)\right\}.$$
Now let $D = \{0,1,\dots,p-1\}$, and give $D$ the discrete topology; I claim that $B(0,r)$, as a subspace of $\mathbb{Q}_p$, is homeomorphic to the product space $D^\omega$, which is of course compact. (In fact it’s a Cantor set.) The homeomorphism is the obvious one: $$h:D^\omega\to B(0,r):\langle x_k:k\in\omega\rangle\mapsto \sum_{k\ge r}x_{k-r}p^k.$$
Clearly $h$ is a bijection: $$h^{-1}:B(0,r)\to D^\omega:x=\sum_{k\ge r}x_kp^k\mapsto \langle x_{k+r}:k\in\omega\rangle\;.$$
$B(0,r)$ has a base of clopen sets of the form $B(x,s)$, where $x\in B(0,r)$ and $s\ge r$. Fix such a $B(x,s)$, with $x=\sum_{k\ge r}x_kp^k$. If $y=\sum_{k\ge r}y_kp^k\in B(0,r)$, then $|x-y|_p = p^{-m}$, where $m=\min\{k\ge r:x_k\ne y_k\}$, so $y \in B(x,s)$ iff $m\ge s$. In other words, $$B(x,s) = \bigg\{y\in B(0,r):\min\{k\ge r:y_k\ne x_k\}\ge s\bigg\},$$ and therefore $$h^{-1}[B(x,s)] = \bigg\{\langle y_{k+r}:k\in\omega\rangle:(\forall k<s-r) \big[y_{k+r}=x_{k+r}\big]\bigg\},$$ which is a basic open set in the product $D^\omega$. Thus, $h$ is a continuous bijection. The sets of the form $h^{-1}[B(x,s)]$ are a base for $D^\omega$, so the same calculation shows that $h^{-1}$ is continuous and hence that $h$ is a homeomorphism.