Bijection between irreducible representations and conjugacy classes of finite groups
This is a different take on Steven Landsburg's answer. The short version is that conjugacy classes and irreducible representations should be thought of as being dual to each other.
Fix an algebraically closed field $k$ of characteristic not dividing the order of our finite group $G$. The group algebra $k[G]$ is a finite-dimensional Hopf algebra, so its dual is also a finite-dimensional Hopf algebra of the same dimension; it is the Hopf algebra of functions $G \to k$, which I will denote by $C(G)$. (The former is cocommutative but not commutative in general, while the latter is commutative but not cocommutative in general.) The dual pairing $$k[G] \times C(G) \to k$$
is equivariant with respect to the action of $G$ by conjugation, and it restricts to a dual pairing $$Z(k[G]) \times C_{\text{cl}}(G) \to k$$
on the subalgebras fixed by conjugation; $Z(k[G])$ is the center of $k[G]$ and $C_{\text{cl}}(G)$ is the space of class functions $G \to k$. Now:
The maximal spectrum of $Z(k[G])$ can be canonically identified with the irreducible representations of $G$, and the maximal spectrum of $C_{\text{cl}}(G)$ can be canonically identified with the conjugacy classes of $G$.
The second identification should be clear; the first comes from considering the central character of an irreducible representation. Now, the pairing above is nondegenerate, so to every point of the maximal spectrum of $Z(k[G])$ we can canonically associate an element of $C_{\text{cl}}(G)$ (the corresponding irreducible character) and to every point of the maximal spectrum of $C_{\text{cl}}(G)$ we can canonically associate an element of $Z(k[G])$ (the corresponding sum over a conjugacy class divided by its size).
In general there is no natural bijection between conjugacy classes and irreducible representations of a finite group. To see this think of abelian groups for example. The conjugacy classes are the elements of the group, while the irreducible representations are elements of the dual group. These are isomorphic, via the Fourier transform, but not canonically.
Let $k$ be an algebraically closed field whose characteristic is either zero or prime to the order of $G$.
Then the center of the group ring $kG$ has one basis in natural bijective correspondence with the set of irreducible representations of $G$ over $k$, and another basis in natural bijective correspondence with the conjugacy classes of $G$.
Namely:
1) $kG$ is semisimple (this is called Maschke's Theorem) and Artinian, so it is a direct sum of matrix rings over division rings, hence (because $k$ is algebraically closed) a direct sum of matrix rings over $k$. There is (up to isomorphism) one irreducible representation for each of these matrix rings. Those representations are therefore in natural one-one correspondence with the central idempotents that generate those matrix rings, and these form a basis for the center.
2) For each conjugacy class, we can form the sum of all elements in that conjugacy class. The resulting elements of $kG$ form a basis for the center.
This gives a (non-natural) bijection between irreducible representations and conjugacy classes, because there is a (non-natural) bijection between any two bases for a given finite-dimensional $k$-vector space. I do not see any way you can make this natural.