Motivation behind the definition of GCD and LCM
In Euclidean domains, such as $\mathbb Z$ and $\rm\:F[x],\:$ the gcd is often defined as a common divisor that is "greatest" as measured by the Euclidean valuation, here $\rm\:|n|\:$ and $\rm\:deg\ f(x)\:$ resp. But general integral domains may not come equipped with such structure, so in this more rarified atmosphere one is forced to rely only on the divisibility relation itself to specify the appropriate extremality property. Namely, one employs the following universal dual definitions of LCM and GCD
Definition of LCM $\quad$ If $\quad\rm a,b\mid c \iff [a,b]\mid c \quad$ then $\,\quad\rm [a,b] \;$ is an LCM of $\:\rm a,b$
Definition of GCD $\quad$ If $\quad\rm c\mid a,b \iff c\mid (a,b) \quad$ then $\quad\rm (a,b) \;$ is an GCD of $\:\rm a,b$
Notice $\rm\,(a,b)\mid a,b\,$ by the direction $(\Rightarrow)$ for $\rm\,c=(a,b),\,$ i.e. $\rm\,(a,b)\,$ is a common divisor of $\rm\,a,b.\,$ Conversely direction $(\Leftarrow)$ implies $\rm\,(a,b)\,$ is divisible by every common divisor $\,\rm c\,$ of $\rm\,a,b\,$ therefore $\rm\,(a,b)$ is a "greatest" common divisor in the (partial) order given by divisibility. Similarly, dually, the lcm definition specifies it as a common multiple that is "least" in the divisiility order.
One easily checks that this universal definition is equivalent to the more specific notions employed in Euclidean domains such as $\,\Bbb Z\,$ and $\rm\,F[x].$
Such universal definitions frequently enable one to give slick bidirectional proofs that concisely unify both arrow directions, e.g. consider the following proof of the fundamental lcm $*$ gcd law.
Theorem $\rm\;\; (a,b) = ab/[a,b] \;\;$ if $\;\rm\ [a,b] \;$ exists.
Proof $\ \ \ \rm d\mid (a,b)\iff d\:|\:a,b \iff a,b\:|\:ab/d \iff [a,b]\:|\:ab/d \iff d\:|\:ab/[a,b] $
Many properties of domains are purely multiplicative so can be described in terms of monoid structure. Let R be a domain with fraction field K. Let R* and K* be the multiplicative groups of units of R and K respectively. Then G(R), the divisibility group of R, is the factor group K*/R*.
R is a UFD $\iff$ G(R) $\:\rm\cong \mathbb Z^{\:I}\:$ is a sum of copies of $\rm\:\mathbb Z\:.$
R is a gcd-domain $\iff$ G(R) is lattice-ordered (lub{x,y} exists)
R is a valuation domain $\iff$ G(R) is linearly ordered
R is a Riesz domain $\iff$ G(R) is a Riesz group, i.e. an ordered group satisfying the Riesz interpolation property: if $\rm\:a,b \le c,d\:$ then $\rm\:a,b \le x \le c,d\:$ for some $\rm\:x\:.\:$ A domain $\rm\:R\:$ is Riesz if every element is primal, i.e. $\rm\:A\:|\:BC\ \Rightarrow\ A = bc,\ b\:|\:B,\ c\:|\:C,\:$ for some $\rm b,c\in R.$
For more on divisibility groups see the following surveys:
J.L. Mott. Groups of divisibility: A unifying concept for integral domains and partially ordered groups, Mathematics and its Applications, no. 48, 1989, pp. 80-104.
J.L. Mott. The group of divisibility and its applications, Conference on Commutative Algebra (Univ. Kansas, Lawrence, Kan., 1972), Springer, Berlin, 1973, pp. 194-208. Lecture Notes in Math., Vol. 311. MR 49 #2712
The motivation comes from generalizing the definition to more abstract rings (technically, integral domains).
The GCD of two elements $a$ and $b$ is indeed a greatest element of the set $S$ of common divisors of $a$ and $b$. However, the twist lies in the way we interpret the qualifier "greatest". As J.M. points out, many rings of interest do not admit an interesting linear order, so it is not immediately clear what the "greatest element" of a set $S$ could mean.
Let's not give up though. In our context, it seems natural to endow the ring with a preorder induced by divisibility: $x \preccurlyeq y$ if and only if $x$ divides $y$. [In fact, one may pretend that $\preccurlyeq$ is a partial order by quotienting out by the units in the ring.] At first, this seems a little unsatisfactory because this relation is partial; i.e., not every pair of elements (e.g., $42$ and $72$) are comparable through divisibility. However, this turns out to be the correct thing to study.
Armed with this pre-order, we can define a GCD of $a$ and $b$ to be any greatest element of the set $S$ of all common divisors of $a$ and $b$. One can verify that this is just a restatement of the second definition in the question.
Having motivated the definition, I must warn you about a couple of caveats:
It's certainly not that case that every ring has GCDs defined for all pairs of elements. Nevertheless many interesting ones do: e.g., one can compute GCDs of integers, of Gaussian integers, of polynomials and so on.
Echoing GEdgar's remark above, for the special case of the positive integers, we now have two competing definitions of GCD, depending on the meaning of "greatest". Fortunately though, it turns out that these two definitions match, and hence we can use either definition as is convenient.
For two reasons:
1) You can calculate the GCD and LCM without knowing anything about prime numbers and prime factorization.
2) What is the GCD of 13121341 and 234132431 ?
Prime factorization cannot help you here, the prime factorization problem is pretty hard even for computers. Actually most of the internet security is based on the fact that there is no known algorithm for factoring large numbers in reasonable time.
You can calculate this GCD using the Euclidean Algorithm, which can be proven easily using the second definition, and has nothing to do with prime factorization.
I think the second reason is usually the main one...
Actually you are right except for one case.
$\gcd(0,0) = 0$
The divisors of $0$ are $D_0 = \{0, \pm 1, \pm 2, \dots \}$ and there is no greatest element of this set. But clearly $d'|0$ and $d'|0 \implies d'|0$. So $\gcd(0,0) = 0$.
What the second definition captures that the first does not is that $D_m \cap D_n = D_{\gcd(m,n)}$ where $D_x$ represents the set of all divisors of $x$. In words, you find the set of all divisors of $m,$ the set of all divisors of $n,$ and then find the set of all numbers that those two sets have in common. that set is the set of all divisors of $\gcd(m,n)$.