How can one talk about gcd in the context of complex numbers where order doesn't exist?

This is a great question, and perhaps deceptively deep.

One way to define the greatest common divisor of two Gaussian integers is as follows: given $z,w \in \mathbb{Z}[i]$, we call $g \neq 0$ a greatest common divisor of $z$ and $w$ if $g$ has the following property:

If $d \mid z$ and $d \mid w$, then necessarily $d \mid g$.

You might note that I mentioned that such a Gaussian integer is a greatest common divisor instead of the greatest common divisor --- this is because there isn't a single greatest common divisor. Unlike in the regular integers, there isn't an ordering (as you mention), so there is no good way to distinguish between different associates of the same integer.

For example, the greatest common divisors of $2$ and $4$ (in the Gaussian integers) are $2, 2i, -2i, -2$. Any one of these four could have been called a greatest common divisor.

This is a very general definition that works in many contexts, not just the Gaussian integers. [This works over $\mathbb{Z}$ too - you should try and prove it if you haven't].

Another way to define the greatest common divisor is to say $g$ is a greatest common divisor of $z,w \in \mathbb{Z}[i]$ if

1. $g \mid z$ and $g \mid w$, and
2. If $d \mid g$ and $d \mid w$, then $N(d) \leq N(g)$.

That is, a greatest common divisor is a common divisor of greatest norm.

For those with the mathematical maturity, another way of defining greatest common divisors relies on thinking of the integers as a ring. Then a greatest common divisor of $a$ and $b$ is a generator $g$ of the principal ideal containing $a,b$. That is, $\langle g \rangle = \langle a, b \rangle$. The existence of such principal ideals is closely related to what it means to have unique factorization. [This is also related to why being a Euclidean domain is stronger than being a unique factorization domain. Thanks to quid who noted an error in my answer in the comments below].

For a bit more about Gaussian integers and number theory, I note that I wrote up a few notes for my students of number theory once upon a time. Some others have found these notes useful.

We can partially order the Gaussian integers in terms of divisibility: $$a \ge b \iff \exists c \in \mathbb{Z}[i] \text{ such that } a = bc$$

in this case we say $b$ divides $a$, written $b|a$. So when we say that $d = \gcd(a,b)$ we mean that if $\tilde{d}|a$ and $\tilde{d}|b$ then $\tilde{d}|d$. This is the sense in which the gcd is "greatest". As for computing gcd's in the Gaussian integers the other (well written) answers above (and/or bellow) tell us that the Gaussian integers is a euclidean domain and so we can essentially use long division to nut it out.