Let $\dim(M)=2n$.
$\newcommand{\b}[1]{\begin{bmatrix}#1\end{bmatrix}}$
Let $S=\b{0 &I_n\\I_n &0}$. Then $S^{-1}=S^*=S$.
$$S^{-1}MS=-M^*.$$
Recall that $\Bbb C^{2n\times1}$ is a Hermitian space with inner product defined by $\langle x, y\rangle=x^\dagger y$.
Let $\kappa:\Bbb C^{2n\times1}\to\Bbb C^{2n\times1}$, $\kappa(x)=Sx^*$, i.e., $\kappa\left(\b{a\\b}\right)=\b{b^*\\a^*}.$
$\kappa$ is an antiunitary operator and $\kappa^{-1}=\kappa$.
Let $\{0\}\not=M_\lambda=\{x\in\Bbb C^{2n\times1}\mid Mx=\lambda x\}$, the $\lambda$-eigenspace of $M$.
Since $M$ is Hermitian, $\lambda\in\Bbb R$ and $\Bbb C^{2n\times1}=\bigoplus M_{\lambda}$.
Suppose $x\in M_{\lambda}$.
Since $$MSx^*=S(S^{-1}MS)x^*=S(-M^*)x^*=-S(Mx)^*=-S(\lambda x)^*=-\lambda Sx^*,$$
we have $\kappa(x)\in M_{-\lambda}$. Hence $\kappa$ induces an antiunitary isomorphism between $M_{\lambda}$ and $M_{-\lambda}$.
Let $\lambda_i$, where $1\le i\le k$ and $k\ge0$ be all positive eigenvalues of $M$.
Let $B_{\lambda_i}$ be an orthonormal basis of $M_{\lambda_i}$.
Let $B_{-\lambda_i}=\left\{\kappa(x)\mid x\in B_{\lambda_i}\right\}$.
We can see that $B_{-\lambda_i}$ is an orthonormal basis of $M_{-\lambda_i}$.
Note that $\kappa$ induces an antiunitary operator on $M_0$. Let us choose a "$\kappa$-paired" orthonormal basis of $M_0$.
Let $R_1=M_0$. Starting from $t=1$, repeat the following procedure as long as $R_t$ is not $\{0\}$. We will keep $R_t$ as an even-dimensional $\kappa$-invariant $\Bbb C$-linear subspace of $M_0$.
- Suppose we can find $x\in R_t$ such that $x$ and $\kappa(x)$ are $\Bbb C$-linear independent.
Let $\mathscr Z_t$ be the $\Bbb C$-linear space spanned by $x$ and $\kappa(x)$.
Let $R_{t+1}$ be the $\Bbb C$-linear subspace of $R_t$ that is orthogonal to $\mathscr Z_t$. $\dim(R_{t+1})$ is even since it is $ \dim(R_{t})-2$.
Verify that $\kappa$ induces an antiunitary operator on $\mathscr Z_t$ and $R_{t+1}$.
Thanks to the linear independence of $x$ and $\kappa(x)$, we can find $0\not=y\in\mathscr Z_t$ such that $y$ and $\kappa(y)$ is orthogonal. Let $z_t=y/||y||$.
$\{z_t, \kappa(z_t)\}$ is an orthonormal basis of $\mathscr Z_t$.
Add $1$ to $t$.
- Otherwise for all $x\in R_t$ and $x$ and $\kappa(x)$ are $\Bbb C$-linear dependent.
We claim that if $0\not=x$ and $\kappa(x)$ are $\Bbb C$-linear dependent, then $x=\b{u\\e^{i\Theta}u}$ for some $u\in\Bbb C^{n\times1}$ and $\Theta\in \Bbb R$. The proof is straightforward.
Since $R_t$ is even-dimensional, there are $x,y\in R_t$ that are $\Bbb C$-linear independent. Then either $x+y$ and $\kappa(x+y)=\kappa(x)+\kappa(y)$ are not $\Bbb C$-linear dependent, or $x-iy$ and $\kappa(x-iy)=\kappa(x)-i\kappa(y)$ are not $\Bbb C$-linear dependent.
This contradicts the assumption of this case. Hence, this case does not exist.
Since the dimension of $R_t$ decreases by $2$ at each iteration, the procedure above will run $\dim(M_0)/2$ times.
We obtain that $M_0$, as an orthogonal sum of $\mathscr Z_t$, $t=1,\cdots, \dim(M_0)/2$, has an orthonormal basis $z_1, \cdots, z_{\dim(M_0)/2}, \kappa(z_1), \cdots, \kappa(z_{\dim(M_0)/2})$.
Let $\cup B_{\lambda_i}=\{w_1, \cdots, w_{n-\dim(M_0)/2}\}$.
Let $T$ be the following unitary matrix $$\b{w_1, \cdots, w_{n-\dim(M_0)/2}, z_1, \cdots, z_{\dim(M_0)/2}, \kappa(w_1), \cdots, \kappa(w_{n-\dim(M_0)/2}), \kappa(z_1), \cdots, \kappa(z_{\dim(M_0)/2})}$$
Then $T$ is of the required form $\b{\gamma &\mu\\\mu^* &\gamma^*}$ and
$$MT=\b{\Lambda & 0 & 0 & 0\\0 & 0 & 0 & 0\\0&0 &-\Lambda& 0\\0 & 0 & 0 &0}T=\b{d &0 \\ 0 & -d}$$
where $\Lambda$ is a diagonal real matrix with $\lambda_i$'s on the diagonal, and $d$ is the $n$-dimensional diagonal real matrix $\b{\Lambda & 0\\ 0 & 0 }$.
Since $T^\dagger M(T^\dagger)^\dagger=T^\dagger MT=\b{d &0 \\ 0 & -d}$, and $T^\dagger$ is an unitary matrix of the form $\b{\gamma &\mu\\\mu^* &\gamma^*}$ as well, we have done.
