If $ \operatorname{Tr}(M^k) = \operatorname{Tr}(N^k)\;\forall 1\leq k \leq n$, then how do we show the $M$ and $N$ have the same eigenvalues?

$M$ and $N$ have the same generalized eigenvalues (with multiplicity) if and only if their characteristic polynomials are the same. Thus it suffices to show that the power sums $T_k = \sum _{i=1}^{n} \alpha^k_i$ for $k = 1$ to $n$ generate the ring of symmetric polynomials (the coefficients of the characteristic polynomial are symmetric polynomials in the eigenvalues). This is a result due to Newton. For example, if $S_k$ is the usual $k$-th elementary symmetric polynomial (the sum of all products of $k$ distinct $\alpha_i$), then one has:

$$S_1 = \sum \alpha_i = T_1,$$

$$S_2 = \sum_{i > j} \alpha_i \alpha_j = \frac{1}{2} \left( \left(\sum \alpha_i\right)^2 - \sum \alpha^2_i \right) = \frac{1}{2}(T^2_1 - T_2)$$

More generally, one has:

$$\log \sum_{k=0}^{n} S_k X^k = \log \prod_{i=1}^{n} (1 + \alpha_i X) = \sum_{k=1}^{n} \log(1 + \alpha_i x)$$

which, expanding the logarithm, becomes:

$$ \sum_{k=1}^{n} \sum_{j=1}^{\infty} \frac{\alpha^j_i (-1)^{j-1} X^j}{j} = \sum_{j=1}^{\infty} \frac{T_j (-1)^{j-1} X^j}{j}$$

In particular, from the $S_k$ one can determine all the $T_k$, and from the $T_k$ (for $k = 1$ to $n$) one can determine the $S_k$ (and hence all the $T_k$ as well).

This even shows that the ring generated by $T_k$ over any ring $R$ for $k = 1$ to $n$ is the same as the ring generated by $S_k$ for $k = 1$ to $n$, as long as $n!$ is invertible in $R$. So the result also holds for any field of characteristic $p > n$. It is false if $p \le n$ - for example, the identity $p \times p$ matrix and all its powers has trace $0$, which is the same as the zero matrix.

What about this one?

We know that if $\psi_A(x) = |xI_n - A| = x^n+c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots+c_1x+c_0I_n$ be characteristic polynomial of $A$ (thus $c_0 = (-1)^n|A|$), then the coefficients are given by $$c_{n-m}=\frac{(-1)^m}{m}\left| \begin{array}{ccccc} t_1 & m-1 & 0 & \cdots & 0 \\ t_2 & t_1 & m-2 & \cdots & 0 \\ \vdots & \vdots & & & \vdots \\ t_{m-1} & t_{m-2} & t_2 & t_1 & 1 \\ t_m & t_{m-1} & t_3 & t_2 & t_1 \\ \end{array} \right|$$ where $t_r:= \operatorname{tr}(A^r)$.

Assume that $\psi_{M}(x)=x^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\cdots+a_1x+a_0I_n$ and $\psi_N(x)=x^n+b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\cdots+b_1x+b_0I_n$. Then $$a_r=b_r$$ (by using $\operatorname{tr}(M^k) = \operatorname{tr}(N^k)$ and the above determinant).

Hence $\psi_M(x)=\psi_N(x)$ which means $M$ and $N$ will have same eigenvalues.