Let me go back to the beginning and state the question more clearly. We have a quantum system in which there are two angular momenta $\vec L$ and $\vec S$ that are coupled, so that $\vec J = \vec L + \vec S$ is conserved. Then, $J^2$, $L^2$, $S^2$ mutually commute and can be used as good quantum numbers. In the Hydrogen atom example, $S = 1/2$. This makes the problem much simpler, and so I will work with this example, although the method can be generalized to any $S$.
In the following, I will assume that $L$ and $S$ are fixed and I will not write $L$ and $S$ explicitly. The value of $J$ will depend on the relative orientation of $\vec L$ and $\vec S$. There are two possibilities: $J = L+1/2$ and $J = L - 1/2$.
There are two ways to label the states of the system. We can use the labels of total angular momentum $J, m_j$ or we can use the labels of the z angular momentum for $L$ and $S$, $m_\ell, m_s$. Since $J$ is the sum of $L$ and $S$, $m_j = m_\ell + m_s$. Since $S = 1/2$, $m_s = \pm 1/2$.
The total Hilbert space has dimension $2 (2 L + 1)$. But this is divided into 2-dimensional subspaces that do not mix with one another. A typical subspace contains the states
$$ | J = L+{1\over 2}, m_j\rangle \qquad | J = L - {1\over 2}, m_j\rangle $$
or, in the $m_\ell, m_s$ basis,
$$ | m_j-{1\over 2}, +{1\over 2}\rangle \qquad | m_j + {1\over 2}, -{1\over 2}\rangle \ . $$
These pairs of states give two different orthogonal bases for the same Hilbert space. They are related by a unitary transformation. The Clebsch-Gordan coefficients are defined to be the elements of this $2\times 2$ unitary matrix. Clebsch-Gordan coefficients can be written $c_{m_j,+}$, etc., as in the question, but it is much more transparent to write them as explicitly indicating this change of basis,
$$ \langle L S m_\ell m_s|LS J m_j\rangle \quad \mbox{or, simply} \quad \langle m_\ell m_s|J m_j\rangle \ . $$
In the standard conventions, Clebsch-Gordon coefficients are real-valued. Then the first equation of the question can be rewritten
$$ | J m_j> = \langle (m_j-{1\over 2}) (+{1\over 2})|J m_j\rangle \ |(m_j-{1\over 2})(+{1\over 2})\rangle \\ + \langle (m_j+{1\over 2}) (-{1\over 2})|J m_j\rangle \ |(m_j+{1\over 2}) (-{1\over 2})\rangle \ , $$
which is much more transparent.
Up to this point, everything is formalism. But we are now in a good position to answer the question of how to compute the Clebsh-Gordan coefficients. The arguments below can be found in many textbooks on quantum mechanics. I recommend especially Gordon Baym's "Lectures on Quantum Mechanics", which has a whole chapter (Chapter 15) devoted to the addition of angular momenta.
The key is that, while most of the subspaces are 2-dimensional, there are two special subspaces that are 1-dimensional. There is only one state with $m_j = J+1/2$,
$$ | J = (L+{1\over 2}), m_j = (L+{1\over 2}) \rangle = | L, (+{1\over 2})\rangle \ ,$$
and there is only one state with $m_j = -L- 1/2$,
$$ | J= (L+{1\over 2}), m_j = -(L+{1\over 2})\rangle = \pm | (-L), (-{1\over 2})\rangle \ ,$$
Then
$$ \langle (L+{1\over 2})(L+{1\over 2}) | L(+1/2)\rangle = 1 \qquad
\langle (-L-{1\over 2}), (-L-{1\over 2}) | (-L)(-1/2)\rangle = \pm 1 $$
(The relative sign $\pm$ has to be worked out by the process given below.)
Taking the first equation here as a starting point, we apply the operator $J^- = (J^x - i J^y)$. $J^-$ commutes with $J^2$, so the action of this operator preserves $J$. On a state $|Jm\rangle$, it can be shown
$$ J^- \ |jm\rangle = [ j(j+1) - m(m-1)]^{1/2} | j (m-1)\rangle
\ . $$
This equation appears in the proof of the quantization of angle momentum that can be found in any quantum mechanics text. But here we will use it as a tool. Apply $J^-$ to $|(L+{1\over 2})(L+{1\over 2})\rangle$,
$$ J^- |(L+{1\over 2})(L+{1\over 2})\rangle = \sqrt{2L+1} |(L+{1\over 2})(L-{1\over 2})\rangle\ . $$
Now write $J^- = L^- + S^-$ and apply this to $| L, (+{1\over 2})\rangle$,
$$ J^- | L, (+{1\over 2})\rangle = \sqrt{2L}\cdot | (L-1), (+ {1\over 2})\rangle + 1 \cdot | L, (-{1\over 2})\rangle $$
Now we have found that
$$ \sqrt{2L+1} |(L+{1\over 2})(L-{1\over 2})\rangle = \sqrt{2L}\cdot | (L-1), (+ {1\over 2})\rangle + 1 \cdot | L, (-{1\over 2})\rangle $$
and so we can identify
$$ \langle (L-1)(+{1\over 2})| (L+{1\over 2}) (L-{1\over 2})\rangle =\sqrt{{2L\over 2L+1}} \qquad \langle L(-{1\over 2})| (L+{1\over 2})(L -{1\over 2})\rangle =\sqrt{{1\over 2L+1} }\ . $$
There is only one state in the 2-dimensional subspace that is orthogonal to
$|(L+1/2)(L-1/2)\rangle$. That is the state with $J = L-1/2$ and $m_j = L-1/2$. Then that state must be the one orthogonal to the above,
$$ |(L-{1\over 2})(L-{1\over 2})\rangle = - \sqrt{{1\over 2L+1}}\cdot | (L-1), (+ {1\over 2})\rangle + \sqrt{{2L\over 2L+1}} \cdot | L, (-{1\over 2})\rangle $$
up to an overall sign, which can only be fixed by convention.
Then we can identify
$$ \langle (L-1)(+{1\over 2})| (L+{1\over 2}) (L-{1\over 2})\rangle = - \sqrt{{1\over 2L+1}} \qquad \langle L(-{1\over 2})| (L+{1\over 2})(L -{1\over 2})\rangle =\sqrt{{2L\over 2L+1}}\ . $$
We can continue similarly to the states with $m_j = L-3/2$ by applying $J^-$ one more time. In a similar way, we can compute all of the Clebsch-Gordan coefficients needed for this problem.
It is a nice exercise to carry out this process explicitly for a fixed value of $L$, for example, $L=1$, and compare your results to those in a reference table. A nice table can be found in Griffiths' Quantum Mechanics book, Table 4.8, or at the original source:
https://pdg.lbl.gov/2020/reviews/rpp2020-rev-clebsch-gordan-coefs.pdf .