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:

lotsof encyclopedic treatments of the representation theory but no half-page introductions known to me. – Ilya Nikokoshev Nov 9 '09 at 22:32