For any group character $\chi: G \to \mathbb{C}$, the function $\chi(g^k)$ is an integer-linear combination of other group characters in $\mathrm{Irr}(G)$. There doesn't seem to be a general way of finding the expansion in terms of the basic representations.
In the case of the symmetric group $S_n$, the permutation representation (dim = n ) decomposes into the standard representation (dim = n-1) and the trivial representation (dim = 1). $\mathrm{perm} = (n) + (n-1,1)$. I like this representation b/c it's character is the number of fixed points.
I would like to decompose $\chi_{\mathrm{perm}}(g^k)$ into an integer combination of irreducible characters. Fulton-Harris gives a formula for the exterior powers of the standard representation: $\wedge^d (n-1,1)= (n-d,d)$. I would settle for expanding $\chi_{(n-1,1)}(g^k)$ into irreducible characters.
In terms of eigenvalues these are the elementary symmetric polynomials $e_1 = \lambda_1 + \dots \lambda_n$ and $e_2 = \sum_{i < j} \lambda_i \lambda_j$ and I'm looking for the symmetric powers $\lambda_1^k + \dots + \lambda_n^k$. Maybe there's a way using Newton's identities, but that doesn't explain how to expand the tensor product into irreducibles.
Probably, $\chi_{\wedge^k \mathrm{perm}}(g)$ counts fixed k-element subsets of {1,2,…,n}, which is different than $\chi_{\mathrm{perm}}(g^k)$ counting (possibly degenerate) fixed $k$-cycles.
Best Answer
Let $\chi$ be the character of some finite-dimensional $G$-representation $V$, for $G$ a finite group. The virtual character $\chi(g^n)$ can be found using a categorified version of the cycle index of the symmetric group $S_n$:
$$\chi(g^n) = \frac{1}{n!} \sum_{\lambda} \pm C_{\lambda} \mathbb{S}_{\lambda} V,$$
where the sum runs over all partitions of $n$, $C_{\lambda}$ stands for the size of the conjugacy class associated with $\lambda$, $\mathbb{S}_{\lambda}$ is a Schur functor, and the sign depends on the parity of the number of even parts of $\lambda$. I'm sure you are familiar with the special case of this formula
$$ \chi(g^2) = \frac{1}{2} \left[ \mathbb{S}_{2} V - \mathbb{S}_{1+1} V \right] , $$
which is just another way to talk about Frobenius-Schur indicators. In fact, these characters are called "higher Frobenius-Schur indicators," which seems like a reasonable name.
Now the bad news. Nobody knows in general what Schur functors do to irreducible representations. Even in the special case of the standard representation of the symmetric group, I do not share Bruce Westbury's optimism about decomposing exterior powers into irreducibles, since every Schur functor may be written as a $\mathbb{Z}$-linear combination of tensor products of exterior power functors, and the Littlewood-Richardson coefficients would then allow us to compute arbitrary plethysm in the symmetric group.
As a last point, it is certainly false that $\chi_{\wedge^k \mbox{perm}}$ counts fixed $k$-element subsets. Anyway, it is not hard to show that the "choose k" functor from permutation representations is actually a virtual Schur functor.