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 $\mathbb C[G]$

To prove this, take any nontrivial representation $R$ and show that $\mathrm{dim}\\,\mathrm{Hom}\\,(R, \mathbb C[G]) >0$.

> (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. I would like to point out the following book if you would be interested in learning more about different parts of  the subject:

* [*Introduction to representation theory*][1], write-up of lectures by Pavel Etingof to high-school students and MIT undergraduates. This books covers more material, but it has finite groups in Chapter 3.



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