Arguably the most important fact about normal matrices is the spectral theorem, which tells that they are unitarily diagonalizable; that is, there exist $U, \Lambda \in \mathscr M_n(\mathbf C)$ with $U \adj U = \adj U U = \mathbf 1$ and $\Lambda$ diagonal such that $$ A = U\Lambda \adj U; $$ hence, we look for a polynomial $p$ such that $$ \begin{align*} p(A) &= Up(\Lambda) \adj U = U \begin{pmatrix} p(\lambda_1) & & &\\ & p(\lambda_2) & &\\ & & \ddots &\\ & & & p(\lambda_n) \end{pmatrix} \adj U = U \begin{pmatrix} \bar \lambda_1 & & &\\ & \bar \lambda_2 & &\\ & & \ddots &\\ & & & \bar \lambda_n \end{pmatrix} \adj U = \adj A\\ \implies p(\lambda_i) &= \bar \lambda_i. \end{align*} $$ Let now, without loss of generality, $\lambda_1, \lambda_2, \ldots, \lambda_k$ be the $k$ distinct eigenvalues of $A$, and set $$ p(t) = q_0 + q_1 t + q_2 t^2 + \cdots + q_{k-1} t^{k-1}; $$ we want $p$ to be the interpolating polynomial of the points $(\lambda_i, \bar \lambda_i)$, so its coefficients are given by the equation $$ \begin{pmatrix} 1 & \lambda_1 & \lambda_1^2 & \cdots & \lambda_1^{k-1}\\ 1 & \lambda_2 & \lambda_2^2 & \cdots & \lambda_2^{k-1}\\ 1 & \lambda_3 & \lambda_3^2 & \cdots & \lambda_3^{k-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \lambda_k & \lambda_k^2 & \cdots & \lambda_k^{k-1}\\ \end{pmatrix} \begin{pmatrix} q_0\\ q_1\\ q_2\\ \vdots\\ q_{k-1} \end{pmatrix} = \begin{pmatrix} \bar \lambda_1\\ \bar \lambda_2\\ \bar \lambda_3\\ \vdots\\ \bar \lambda_k \end{pmatrix}, $$ which has a solution because the system matrix is a Vandermonde matrix with distinct entries, and so it is invertible.

Notice first that $A$ commutes with any power of $N$; we can prove this claim inductively, where the base case is the initial assumption, and for the inductive step $$ N^{n+1} A = N N^n A = N A N^n = A N N^n = A N^{n+1}. $$ Extending this result, because matrix product is distributive over addition ($\mathscr M_n(\mathbf C)$ is a ring) $A$ commutes with any linear combination of powers of $N$, in other words, with any polynomial acting on $N$.
Finally, invoking the previous lemma settles the proof: $$ A \adj N = A p(N) = p(N) A = \adj N A. $$