Showing matrices in $SU(2)$ are of form $\begin{pmatrix} a & -b^* \\ b & a^*\end{pmatrix}$

The condition $A^{\ast}A=I$ says that $A$ has orthonormal columns.

Suppose the first column is $v=[\begin{smallmatrix}a\\b\end{smallmatrix}]$. It must have unit norm, so $|a|^2+|b|^2=1$. What can the second column be? It must be orthogonal to the first, which means it must be in the complex one-dimensional orthogonal complement. Thus, if $w$ is orthogonal to $v$, then the possibilities for the second column are $\lambda w$ for $\lambda\in\mathbb{C}$. Since $\det[v~\lambda w]=\lambda\det[v~w]$, only one value of $\lambda$ will make the determinant $1$, hence the second column is unique. So it suffices to check $w=[-b ~~ a]^{\ast}$ works, which is natural to check because in ${\rm SO}(2)$ the second column would be $[-b~~a]^T$.

Using @Omnomnomnom's suggestion $AA^\dagger =A^\dagger A$, we first obtain the relations \begin{align} AA^\dagger: r &= -\frac{su^*}{t^*}\ , \ u= -\frac{tr^*}{s^*} \\ A^\dagger A: r &= -\frac{tu^*}{s^*}\ , \ u= -\frac{sr^*}{t^*} \ . \end{align} Noticing the common factor $\frac{-t}{s^*}$ for $r_{A^\dagger A}$ and $u_{AA^\dagger}$, we put $x:=\frac{-t}{s^*}$.

This allows us to write $u = xr^*$.

Similarly, we have \begin{align} AA^\dagger: s &= -\frac{rt^*}{t^*}\ , \ t= -\frac{us^*}{s^*} \\ A^\dagger A: s &= -\frac{ut^*}{s^*}\ , \ t= -\frac{rs^*}{t^*} \ , \end{align} and $y:= \frac{-u}{s^*}$. Which yields $s = yt^*$.

Hence, so far, we have $$ A = \begin{pmatrix}r & yt^* \\ t & xr^*\end{pmatrix} \ . $$

We now notice that, in fact, we have $$ y = -\frac{u}{r^*} = -\frac{(xr^*)}{r^*} = -x \ . $$

Our matrix now looks like $$ A = \begin{pmatrix}r & -xt^* \\ t & xr^*\end{pmatrix} \ . $$

Now, finally, at last, we use $\operatorname{det}(A) = 1$ to show that $x=1$: \begin{align} \operatorname{det}(A) &= 1 \\ &= x(|r|^2+|t|^2) \\ &= x \cdot 1 \ . \end{align}

We now conclude with $$ A = \begin{pmatrix}r & -t^* \\ t & r^*\end{pmatrix} \ . $$