A generalised proof of the above theorem comes from ring theory. It is useful both in that it applies to objects other than natural numbers, and as it puts the natural number case into context and shows why the above proof works at a deeper level. This is of course just an example of the abstract process of mathematical abstraction.
Anyway, the translation of the theorem into ring theory goes like this :
Suppose we have a ring R which is a principle ideal domain and which contains unity (an identity element under the multiplicitive group, written 1). And suppose we have a and b elements of R. Then there exists an element d in R s.t. d|a, d|b, and if another element c in R is such that c|a and c|b, then c|d. Also, there exist e, f in R s.t. ae + bf = d.
The proof relies on the idea of ideals. First, we consider I := aR + bR. This can quite easily be seen to be an ideal in R. Now, since we said R is a principle ideal domain, this means I is a principle ideal - i.e. there exists d in R s.t. I = dR. We show d satisfies the conditions in the theorem.
Now, aR is a subset of I, and 1 is in R, so a is in I, which means there is some element g of R s.t. dg = a i.e. d|a. Similarly, d|b.
And suppose there exists a c in R s.t. c|a and c|b, and consider the ideal J := cR. We have a, b are in J, and since ideals are closed under multiplication by members of the ring, so are aR and bR. And then using the closure of ideals under addition, we have I = aR + bR is in J, which means d is in J, which means c|d
So d is indeed the gcd of a and b, and the main part of the theorem now comes easily from the way we constructed I - since dR = I = aR + bR, there exist e,f in R s.t. d = ae + bf. Q.E.D.
What the above doesn't prove is the uniqueness of d. That's because we have to assume rather more for that, which reduces the generality of the theorem. For example, the above theorem applies to polynomials over a field, say Q (the rationals). But though a gcd of x+1 and 2x2-2 is x+1, so is 2(x+1), and each divides the other since 2 and 1/2 are both in Q. But that doesn't make the concept of gcd any less powerful here. For example, it applies also to matrix polynomials, which has consequences in the field of linear algebra
Lastly, as a demonstration of the power of abstraction, an example of how our generalised version sheds new light on the area of the original theorem. Two integers are coprime iff their gcd is 1. So we already knew that if a and b are coprime, we can find e and f s.t. ae + bf = 1. But note that from our proof I is now 1R i.e. I = Z itself, the integers. So in fact we can find e and f s.t. ae + bf = g for any integer g at all.