Product of class sums Let $C_i$ be the conjugacy classes of a finite group $G$. Consider the class sums $z_i=\sum_{g\in C_i} g$. It is well known that ${z_i}$ form a basis of the center of the group algebra $\mathbb{C}G$. How can we show that $z_iz_j$ is a $\mathbb{N}$ linear combinations of the $z_i$
 A: Consider the proof that the class sums form a $\Bbb C$-basis for the group algebra $\Bbb C[G]$. Say that
$$x\in Z(\Bbb C[G]), \qquad x=\sum_{g\in G}a(g)g.$$
(Think of the coefficients $a(g)$ as a function $a:G\to\Bbb C$.) Then for any $\sigma\in G$ we have
$$\sigma x\sigma^{-1}=\sum_{g\in G}a(g)\sigma g\sigma^{-1}=\sum_{g\in G}a(\sigma^{-1}g\sigma) g.$$
But since $x$ is central, we know $x=\sigma x\sigma^{-1}$. Comparing coefficients below,
$$\sum_{g\in G}a(g)g=\sum_{g\in G}a(\sigma^{-1} g\sigma)g$$
we find $a(g)=a(\sigma^{-1}g\sigma)$ for all $g,\sigma\in G$, i.e. $a$ is a class function. Thus $a(C)$ makes sense, where we denote by $C$ a conjugacy class of $G$, and so as $C$ ranges over classes we have
$$x=\sum_C a(C)\sum_{g\in C}g.$$
Conversely, class sums are invariant under conjugation by $G$, so any class sum or combination of class sums commutes with any $g\in G$, and hence commutes with every element of $\Bbb C[G]$.
Now if $x,y\in Z(\Bbb C[G])$ then so is $xy$. Therefore if $x$ and $y$ are two class sums, $xy$ must be a $\Bbb C$-linear combination of class sums. But how do we get that it's an $\Bbb N$-linear combination?
Consider instead the semiring $\Bbb N[G]$ (note that our $\Bbb N$ must contain $0$; think about abelian groups $G$ to see this). It is comprised of $\Bbb N$-linear combinations of elements of $G$, with the same obvious rules for addition and multiplication, but this time there aren't additive inverses. The same argument that is written above shows every element of the center $Z(\Bbb N[G])$ (the elements that commute with everything else) are $\Bbb N$-linear combinations of class sums. Clearly the product of any two central elements is central, so the product of class sums must be an $\Bbb N$-linear combination of class sums!
This shows that all of our already-present logic and understanding is perfectly sufficient for the problem at hand, and no new thinking is necessary. One can also give a counting interpretation to the coefficients. If $z_\Gamma=\sum_{g\in \Gamma}g$ denote class sums, and $[g]$ denotes the conjugacy class of an element $g\in G$, then for any three elements $a,b,c\in G$ the coefficient of $z_{[c]}$ in the expansion of the product $z_{[a]}z_{[b]}$ equals $\#\{(x,y)\in G^2:x\sim a,y\sim b,xy=c\}$. Indeed in order to count such a thing with generatingfunctionological thinking, one would naturally look for the coefficient of $c$ in the expansion of $(\sum_{x\sim a}x)(\sum_{y\sim b}y)$!
A: Well, it's not that difficult if you expand the product $z_iz_j$... Then, say you have an element $gh$ in that product with $g\in C_i$ and $h\in C_j$. If we show that all the elements in its conjugacy class appear in the expansion of $z_iz_j$ (the correct number of times), we are done...
Such an element, would be $t^{-1}ght=t^{-1}gt\cdot t^{-1}ht$ which should also appear in $z_iz_j$ since $t^{-1}gt\in C_i$ and $t^{-1}ht\in C_j$.
Evenmore it is not difficult to check that if $gh$ appears many times in the expansion (say because $gh=g'h'$), then $t^{-1}ght$ should appear as many times as well...

Edit: Let me elaborate on that last part:
Say $gh=g_2h_2=\cdots=g_kh_k$ where all the factorizations are different, that is, $gh$ appears $k$-many times in the expansion. Now consider a $t\in G$ such that $t^{-1}ght\neq gh$. We'll show that $t^{-1}ght$ should appear at least $k$ times in the expansion as well (this should be enough, because by symmetry we could apply the same argument for $gh$ appearing more times...).
Of course, we have $t^{-1}ght=t^{-1}g_2h_2t=\cdots=t^{-1}g_kh_kt$. Moreover, each of these products can be written as $t^{-1}g_ih_it=t^{-1}g_it\cdot t^{-1}h_it$. Now, any time that at least one of the pairs $(t^{-1}g_it,t^{-1}g_jt)$ and $(t^{-1}h_it,t^{-1}h_jt)$ contains different elements, both $t^{-1}g_ih_it$ and $t^{-1}g_jh_jt$ appear in the decomposition. But of course, if the two pairs contained the exact same elements, we would have $g_i=g_j$ and $h_i=h_j$, so we wouldn't have gotten two different factorizations of $gh$ to start with...

Edit: As far as the coefficients go, the enumerative interpretation below by whacka is both correct and fruiful, as there is a lot of research about counting factorizations of group elements. However in general, it is very difficult to get a formula for the coefficient of $z_t$.
One reason for that is that apart from the classical Coxeter groups (types A,B,C,D...) and few other examples, we don't even have a consistent way to index the conjugacy classes of a group. 
Moreover, even in the Symmetric group case, where the conjugacy classes have nice combinorial descriptions, we only have partial results. However the theory there is very beautiful and factorizations are connected to particular graphs embedded on surfaces, topologically distinct holomorphic functions, and of course Representation theory.
You can check out this nice paper by Goulden and Jackson, and its many references, for part of the Symmetric group case...
