I came up with this solution to the problem. Does this make sense and is there a better way to going about this problem?
Let $\lambda$ be the real eigenvalue of a normal Matrix $N$. Then, $\overline{\lambda} = \lambda$. Using this and properties of normal operators: \begin{align*} Nx = \lambda x &\Longrightarrow N^\ast Nx = \lambda N^\ast x \\ &\Longrightarrow [N^\ast Nx]^\ast = [\lambda N^\ast x]^\ast \\ &\Longrightarrow N^\ast Nx = \overline{\lambda}Nx = \lambda Nx = \lambda^2 x \\ &\Longrightarrow N^\ast x = \lambda x = Nx \\ &\Longrightarrow N^\ast x = Nx \end{align*}
Now, this proves that $N^\ast x= Nx$ only when $x$ is an eigenvector of $N$. This implies that both $N$ and $N^\ast$ have the same eigenvectors. So any vector in the transformation $N^\ast$ can be represented as a linear combination of the basis consisting of orthogonal eigenvectors of $N$:
$N^\ast v = c_1Nv_1 + \dots + c_nNv_n$, where $v$ is an arbitrary vector in the vector space, $c_1, ..., c_n \in \mathbb{F}$ and $v_1, \dots, v_n$ form the basis of eigenvectors.
As all vectors in the vector space satisfy $N^\ast = N$, by definition, it is proven that $N$ is self-adjoint.
Suppose $N$ is normal. Then \begin{align} \|(N-\lambda I)x\|^2 &=\langle (N^*-\overline{\lambda}I)(N-\lambda I)x,x\rangle \\ &= \langle (N-\lambda I)(N^*-\overline{\lambda}I)x,x\rangle \\ &= \|(N^*-\overline{\lambda})x\|^2 \end{align} Therefore, if $N$ has an orthonormal basis of eigenvectors with real eigenvalues, then $N^*$ has the same orthonormal basis and corresponding real eigenvalues. So $N=N^*$, because this is true on a basis.