To add to D. Savitt's comment: Given $g \in G$ ($G$ a finite group), the element $\rho(g) \in GL(V)$ is diagonalizable over the complex numbers since its minimal polynomial is separable. More specifically, it is a divisor of $x^n - 1$ for some $n$ -- once you have the minimal polynomial, you can compute the projection operators to the various eigenspaces as polynomials in $\rho(g)$, but generally this will require complex coefficients and working in a field which is not algebraically complete will only allow you to project to the kernel of irreducible factors.
Now, a diagonal matrix is determined up to conjugacy by its eigenvalues. And as was pointed out $\mbox{tr } \rho(g^k)$ gives the sum of $k$th powers of the eigenvalues. From these numbers, one can actually recover the set of eigenvalues of the matrix. You can prove this with symmetric functions, but you can also view the spectrum as a measure, and view $\mbox{tr } \rho(g^k)$ as the k'th (complex) moment / Fourier coefficient of the measure. These numbers, together with their complex conjugates give all the Fourier coefficients. They are periodic, so you do not need all of them (you could apply Stone Weierstrass, but that would be very wasteful). We already know the finitely many (say, $n$) candidate eigenvalues from the fact that they satisfy $z^n - 1 = 0$, so we can easily design a polynomial which vanishes on all but one of the eigenvalues and hence determine the multiplicity of each eigenvalue. Namely: $f(z) = \prod_{i \neq j} (z - \lambda_i)$. Then $\mbox{tr } f( \rho(g) )$ (the trace of the projection operator up to a constant) tells you the multiplicity of $\lambda_j$. (Is this exactly the proof through symmetric functions? If not, what is the relationship?)
Inspecting the above argument, it does not seem like the complex numbers play too large a role. But even for a more general unitary representation, the eigenvalues live on a circle and we can view them as a measure $\mu$. We can still obtain $\int z^k d\mu$ for all integers $k$. By Stone-Weierstrass or Fourier inversion, we get the whole spectrum in this way.
This is the extent to which I've thought about the above things so I'd be really happy to know if anyone can say more about it or give more points of view. For example, what very critical type of information do you miss out on by only considering one cyclic subgroup at a time? What about other unitary representations, possibly infinite groups or possibly infinite dimensional?