Euclidean Domain
The definition of a Euclidean Domain, $R$, asserts that you have a Euclidean function $N:R\setminus\{0\}\rightarrow\mathbb N$ so that the algorithm will finish in finitely many steps. This function must satisfy that for $x\in R$ and $d\in R\setminus\{0\}$ there exists $q,r\in R$ such that
$$
x=qd+r
$$
where either $N(r)<N(d)$ or $r=0$.
Euclidean Algorithm
To see how this ensures the algorithm to terminate let us say we are to find $\gcd(a,b)$ for some $a,b\in R$ with $N(a)>N(b)$ just write
$$
a=q_1 b+r_1\\
b=q_2 r_1+r_2\\
r_1=q_3 r_2+r_3\\
\vdots\\
r_{i-2}=q_i r_{i-1}+r_i
$$
using the properties of the Euclidean function in each step so that
$$
N(b)>N(r_1)>N(r_2)>...>N(r_i)>N(r_{i+1})>...
$$
Since the sequence given above is stricly decreasing in $\mathbb N$ by each step in the algorithm we will eventually run out of natural numbers so that we are forced to have $r_n=0$ for some $r_n$ after at most $N(b)$ steps. Then (since a Euclidean Domain is also a Unique Factorization Domain) $\gcd(a,b)=r_{n-1}$ is the 'unique' greatest common divisor of $a$ and $b$ up to multiplication by a unit.