What is $\gcd(0,0)$?

The word "greatest" in "Greatest Common Divisor" does not refer to being largest in the usual ordering of the natural numbers, but to being largest in the partial order of divisibility on the natural numbers, where we consider $a$ to be larger than $b$ only when $b$ divides evenly into $a$. Most of the time, these two orderings agree whenever the second is defined. However, while, under the usual order, $0$ is the smallest natural number, under the divisibility order, $0$ is the greatest natural number, because every number divides $0$.

Therefore, since every natural number is a common divisor of $0$ and $0$, and $0$ is the greatest (in divisibility) of the natural numbers, $\gcd(0,0)=0$.

I answered this already in a comment at MO: "The best way to think about this is that the "gcd" of two natural numbers is the meet of them in the lattice of natural numbers ordered by divisibility. Note that $0$ is the top element in the divisibility order. The meet of the top element with itself is itself. So $0 = \gcd(0, 0)$ is the answer. 'Greatest' is an unfortunate misnomer in this case."

The book Mathematics Made Difficult has a nice little section on this. It should perhaps better be called "highest common factor" (hcf).

Another way to think about this is ideals. The gcd of two natural numbers $a, b$ is the unique non-negative natural number that generates the ideal $\langle a, b \rangle$. So in this case, $\langle 0 ,0 \rangle$ is just the $0$ ideal so the gcd is $0$.