I was trying to prove that if $d \mid a$ and $d \mid b$ then $d \mid \gcd(a,b)$ but wanted a proof that didn't require me to know that $\gcd(a,b) = ax + by$, i.e. that didn't require me to know that the $\gcd(a,b)$ was a linear combination of $a$ and $b$. With that knowledge the proof is trivial (plus for further understanding I wanted a different perspective on this fact that seems to me that doesn't necessarily require that knowledge).
I was trying to think in terms of factorizations to see if I could make it work and these are my current thoughts: if some prime number $p$ divides $a$, and it divides $b$, then it must also divide the GCD. This seems intuitive for primes but if the divisor $d$ is not a prime, I am not sure how to extend the argument. Anyone have any ideas?
Well, if you are willing to use Unique Factorization then, for every prime $p$, $ord_p$ of the gcd is $\min(ord_p(a),ord_p(b))$. But your assumption on $d$ implies that $ord_p(d) \leq \min(ord_p(a),ord_p(b))$.
To elaborate: in the above, $ord_p(n)$ denotes the largest integer $a_p$ such that $p^{a_p}$ divides $n$. Thus, for example, $ord_2{12}=2$, $ord_3{12}=1$. Unique Factorization tells you that $$n=\prod_{p\;prime}p^{ord_p(n)}$$
It follows quickly that $d$ divides $n\;\iff\;ord_p(d)≤ord_p(n)\;\forall\;p$. This quickly implies that $$gcd(a,b)=\prod_{p\;prime}p^{min(ord_p(a),ord_p(b))}$$
I think this should be enough to help you fill in the gaps in my initial argument.
Note: I am not a big fan of this proof, as I think Unique Factorization is a deeper result than the statement about getting the gcd as a linear combination of the terms. Indeed, it is not unusual to use the linear combination principle along the path toward proving Unique Factorization.