A field K is closed if it contains all its algebraic elements. In other words, every polynomial in K[x] splits. For example, the complex numbers form a closed field. Every polynomial with complex coefficients has a complex root u. Divide by x-u and find a smaller polynomial, which also has a root, and continue, until the polynomial splits. Thus it is enough to show every polynomial in K[x] has a root in K.
The closure of K is a minimal field extension of K that splits every polynomial. We will show that the closure is closed.
Let F be the closure of K, and suppose F is not closed. Adjoin u, hence F(u) is algebraic over F. Yet the composition of algebraic extensions is algebraic, so u is algebraic over K. Thus u is contained in F after all, and the closure of a field is closed.
To find the closure of the rationals, adjoin all the roots of all the polynomials with rational coefficients, giving a subfield of the complex numbers that is closed. This is well defined, because we are working within a larger framework, i.e. the complex plane. In general, you have to do some work to prove the closure exists. You have to make sure the adjoined elements aren't all going in different directions. What if the square root of -4 is 2i, and the square root of -9 is 3j, etc. The following set theoretic argument shows the closure of a field exists. It uses the axiom of choice; I don't think that can be avoided. You can skip this if you like.
First bound the size of algebraic extensions of K, so we don't wind up considering the set of all sets. Let c be the cardinality of K. Even if every polynomial is irreducible, there are c + c2 + c3 + … such polynomials. This is countably infinite if c is finite, or it is equal to c otherwise. Upgrade c to infinity if it was finite. At worst each polynomial contributes n roots, and that still leaves the cardinality at c. The closure is no larger than c.
Let s be the cardinal c. Members of s will correspond to elements of K, and elements in the closure of K. consider all 6-tuples of s, along with all embeddings of K into s. The first triple defines addition and the second triple defines multiplication. Only certain relations represent algebraic extensions of K. Restrict attention to these. Order all possible algebraic extensions by containment, i.e. subfield < its containing field. Verify that each chain of extensions is bounded by its union, which is another algebraic extension. Use zorn's lemma to find a maximal field F. Any additional algebraic elements not in F would contradict maximality. And a proper subfield misses certain algebraic elements, and is not closed. Thus F is the closure of K.
If an isomorphism c() takes K onto L, it can be extended to their closures. As before, partially order intermediate extensions and isomorphisms by containment. The < operator requires the two isomorphisms to agree on the smaller subfield. Verify that each chain is bounded by a valid extension and isomorphism, and pick a maximal extension F and isomorphism c(F) onto E, inside the closure of L. If F is not closed, pick an element u not in F and let c map u to a root of the corresponding polynomial over E. That root is present, since the closure of L is closed. Extend the isomorphism to F(u), contradicting maximality. Therefore c() covers the closure.
As a corollary, the closure of K is unique up to isomorphism. It doesn't matter what you call the elements, i.e. the roots of the various polynomials, as long as you are consistent throughout the closure. The structure of the closure is the same.
Now, a quick note for those of you who love set theory. I don't believe we need choice, i.e. zorn's lemma, to build the closure of the rationals or Zp. The polynomials over these fields are countable. Bring them in one at a time and build extension on top of extension. Take the union of this countable ascending chain to find the closure.
Furthermore, we can build an isomorphism between any two such closures. Adjoin the countable roots in a prescribed order and build an ascending chain of isomorphisms; their union being an isomorphism between the two closures.
Other countable fields, such as quotients of polynomials with integer coefficients, can be closed without resorting to choice, and the closure is unique up to isomorphism.