The basic idea is this: if you want gcd($a$, $b$) and $a>b$, then we can instead compute gcd($b, a \bmod b$) and we've made progress. It's progress because when $a>b$, we know $a \bmod b$ is smaller than $b$, it's a remainder after all. And if we make positive inputs smaller and smaller, eventually we must terminate.
The real question is this: why is gcd($a$, $b$) the same as gcd($b, a \bmod b$)?
Well, let's answer an easier question. Instead of trying to wrap your head around $a \bmod b$, let's restate the problem. Why is gcd($a$, $b$) the same as gcd($b, a-b$)? This question is almost the same, but we're using minus instead of mod because it's easier to understand when this stuff is new to you. And mod is just a repeated application of minus anyway, right?
So let's prove the "easier" version. Well, if some divisor $d$ goes evenly into $a$ and $b$, then it must go into their difference $a-b$, right? To be more mathematical, if $a = kd$ and $b=jd$, then $a-b = kd-jd = (k-j)d$ and clearly $d$ goes evenly into $(k-j)d$. Also, if $d$ goes evenly into $(a-b)$ then any $d$ dividing $a$ must divide $b$, so we're done.
If this still isn't clear, draw a number line and convince yourself that two multiples of 3 (for example) are always a multiple of 3 apart. Then convince yourself that any multiple of 3 plus a multiple of 3 must also be a multiple of 3.
Then try it for numbers other than 3.