It's not *entirely* trivial, but here's the sketch of the proof if you would like to finish it yourself. Note that people usually denote complex numbers by $\mathbb C$:

> (1) Every irreducible representation comes as part of regular representation, denoted  $\mathbb C[G]$

To prove this, take any non-trivial representation $R$ and consider $\mathrm{Hom}\,(R, \mathbb C[G])$. A careful examination should show it's non-trivial as well.

> (2) The character $\chi_R$ is a function on $G$ defined as $\chi _ R(g) = \mathrm{tr}\,g| _ R$. Prove that value of any character  on an element of $G$ depends only on element's conjugacy class.

This immediately follows from $\mathrm{tr}\,A = \mathrm{tr}\,BAB^{-1}$ (property of trace).

> (3) Prove that any function on $G$ that depends only on a conjugacy class is a linear combination of some characters $\chi_R$.

I'm not sure I remember how to prove this in an elementary way, but it's doable.

> (4) Prove your statement from (1)-(3).

Indeed, there must be at least as many irreducible representations as there are conjugacy classes and all of them appear in regular representation by (1), so you have your statement.

----

There are many references on representation theory, you can basically pick up any book to answer your question. I would like to point out the following very accessible text if you are be interested in learning more:

* [*Introduction to representation theory*][1], write-up of lectures by Pavel Etingof to high-school students and MIT undergraduates. They cover more material, finite groups are in Chapter 3.  



  [1]: http://arxiv.org/abs/0901.0827