Let $\phi :G \to \text{Aut}(V_0)$ be the regular representation of $G$. Define a representation $\Theta$ of $G \times G$ on $V_0$ by $\Theta(g_1,g_2)e_g=e_{g_1gg^{-1}_2}$, i.e it maps the element $(g_1,g_2)$ to a function that permutes the basis elements as $e_g \mapsto e_{g_1gg^{-1}_2}$.
If $\Phi$ is the character of $\Theta$, how can I prove that $$\Phi(g_1,g_2) = \sum_{\chi \in \text{Irr}(G)} \chi(g_1) \chi(g^{-1}_2)$$
Count the basis elements that $\Theta(g_1,g_2)$ fixes. They fulfill $g_1gg_2^{-1}=g$ and thus $g_1=gg_2g^{-1}$. So the number of fixed points is the number of elements of $G$ that conjugate $g_2$ to $g_1$. If $g_1$ and $g_2$ are in different conjugacy classes, this is $0$, and if they're in the same conjugacy class, it's the order of the group divided by the size of the conjugacy class.
Due to the orthogonality relations, this is exactly what
$$ \sum_{\chi \in \text{Irr}(G)} \chi(g_1) \chi(g^{-1}_2)=\sum_{\chi \in \text{Irr}(G)} \chi(g_1) \chi^*(g_2) $$
yields: If $g_1$ and $g_2$ are in different conjugacy classes, this is the the product of two orthogonal columns of the character table, and thus zero. If they're in the same conjugacy class, it's the product of the corresponding column with itself, which is the order of the group divided by the size of the conjugacy class.