Verlinde's formula "Verlinde's formula" predicts the dimension of the space of conformal blocks of a chiral CFT.
Depending on...
&bullet; which chiral CFT one considers (does one restrict to WZW models, or not?)
&bullet;
 what kind of Riemann surfaces one allows (genus 0? arbitrary genus? with or without punctures?)
&bullet; what definitions of conformal blocks one adopts (sections of a line bundle over $hom(\pi_1(\Sigma),G)$, vertex algebra theoretic)
&bullet; how one writes the answer (in terms of the entries of the S-matrix, or in terms of Lie-theoretic data)

...one gets different mathematical statements.
I am puzzled by the number of different things that go under the name "Verlinde's formula".
I would like to have a list of all proven statements that go under that name, along with, for each one of them, the reference in which the formula was first proved at a mathematical level of rigor. If certain versions of the Verlinde formula are still conjectural, then I would also like to know that.
 A: Verlinde's formula for a modular tensor category says that that tensor product multiplicities $N_{abc}$ for simple objects are given by
$$ \frac{1}{\mathcal{D}^2} \sum_d \frac{S_{ad} S_{bd} S_{cd}}{S_{1d}} $$
where $\mathcal{D}^2$ is the sum of the squares of the dimensions of the simple objects, $S_{xy}$ is the $(x,y)$ entry of the S-matrix (normalized so $S_{11} = 1$), and the sum is over simple objects $d$.
A: This is rather an addition to my comment, as Scott Morrision already give the same answer. 
Usually, what's meant by the Verlinde formula is that the fusion coefficients $N_ {ij}^k$ can be determined by the S-matrix by the formula: 
$$
N_{ij}^k = \sum_l \frac{S_{jl}S_{il} (S^{-1})_{lk}}{S_{0l}}.
$$
While this formula looks mysterious, it basically says that the matrix $S$  diagonalizes the fusion rules, as I want to explain now.
Let us see the fusion coefficients as matrices $N_i$ with coefficients $(N_i)_{ik}=N_{ij}^k$. If we assume that the fusion rules are associative and abelian it follows that these matrices commute, i.e. $N_iN_j=N_jN_i$, so in principle they can be simultaneously diagonalizable, that means there exist a matrix $S$ such that
$$N_i = SD_iS^{-1},$$
where $D_i$ are diagonal matrices with eigenvalues $\lambda^i_j=(D_i)_{jj}$.
Another assumption is that the eigenvalues are non-degenerate. Now $N_0$ is the identity matrix and it holds $SN_0=S$, which implies
$$
S_{il} = \sum_k N_{i0}^k S_{kl}= \sum_{m,k} S_{0m}\lambda^i_m (S^{-1})_{mk}S_{kl} = S_{0l}\lambda^i_l
$$
and it holds:
$$
\lambda^i_l=\frac{S_{il}}{S_{0l}} \quad \Longrightarrow
N_{ij}^k = \sum_l \frac{S_{jl}S_{il} (S^{-1})_{lk}}{S_{0l}}.
$$
So this part is trivial. The insight of Verlinde was, that the modular transformation $\mathcal{S}:\tau\mapsto -1/\tau$ acting on the characters $\chi_\mu(\tau)$ associated to primary fields $\phi_\mu$ diagonalizes the fusion rules, more precisely the matrix $S$ given by:
$$
\chi_k(-1/\tau) = \sum_l S_{kl} \chi_l(\tau)
$$
does the above job for the fusion $i \times j$ of primary fields, i.e. $N_{ij}^k$ fulfilling:
$$
\chi_{i\times l} (\tau) = \sum_k N_{ij}^k \chi_{k}(\tau).
$$
I am probably too young to know about the history, but from what I read this is the reason why this formula is called Verlinde formula. A first proof of this goes back to Moore and Seiberg.
In the categorical approach, the matrix $Y_{ij}$ associated to the Hopf link in a modular tensor category diagonalizes the fusion rules, that gives the case of the formula Scott Morrison mentions. The first time this was proven in the abstract setting of what is called nowadays unitary braided categories was afaik in Rehren: "Braid group statistics and their superselection rules": The Algebraic Theory of Superselection Sectors, D. Kastler ed., Proceedings Palermo 1989, World Scientific 1990, pp. 333-355
A: It's claimed on Page 54 of Bakalov and Kirillov's Lectures on Tensor Categories and Modular Functors that the formula in Scott's post above is first proven in Moore and Seiberg's Classical and Quantum Conformal Field Theory). I've only just grabbed that paper, but equation (A.7) gives a generalization of the formula above to "n-point function characters at genus g" as
$$
dim\, V(g,i_1,\ldots,i_n)=\sum_p\frac{S_{i_1 p}\ldots S_{i_n p}}{S_{0p}\ldots S_{0p}}\left(\frac{1}{S_{0p}}\right)^{2g-2}
$$
which for the case $n=3$,$g=0$ looks like $\mathcal D^2$ times Scott's formula since $N_{ij}^k=dim \, (V_{ij}^k)$ is defined on page 8.

Separately, in section (2.8.3) of DGNO's On Braided Fusion Categories I they provide what they call a Verlinde formula for a premodular category $\mathcal C$ 
$$
S_{XY}S_{XZ}=d(X)\sum_{W\in\mathcal O(\mathcal C)}N_{YZ}^W S_{XW}, \,\,\,\,\,\,\,\,\,\,\,\, X,Y,Z\in \mathcal O(\mathcal C)
$$
equivalent to the one in Scott and Marcel's answers when the S matrix is invertible. Their references for this are 1 as theorem 3.1.12 (which I think should be proposition 3.1.12 in the online edition and prop 3.1.13 in the printed edition, given that the formula is obtained in (3.1.31) as rewriting (3.1.26)) and Muger's On the structure of Modular Categories as Lemma 2.4, though it look like Marcel's Reference from Rehren may be the first to prove this in the pre-modular setting. 
I think this is worth mentioning in its own right because later in 3 section 3.4.2 DGNO prove a "non-spherical analogue of the verlinde formula" as stated in the previous equation, via
$$
\tilde S_{XY}\tilde S_{XZ}=d(X)\sum_{W\in\mathcal O(\mathcal C)}N_{YZ}^W \tilde S_{XW}, \,\,\,\,\,\,\,\,\,\,\,\, X,Y,Z\in \mathcal O(\mathcal C)
$$
where $\mathcal C$ is a braided 
$$
\tilde S_{XY}=\frac{Tr_{-}\otimes Tr_{+}(c_{Y,X}c_{X,Y})}{d_{-}(X)d_{+}(Y)},
$$
$Tr_{-}/Tr_{+}$ and $d_{-}/d_{+}$ are the left/right trace and dimension defined as in their section 2.4.2. This would then be yet another version in a slightly more general context. In the context of a premodular category we have that $S_{XY}=d(X)d(Y)\tilde S_{XY}$.
A: It seems that the previous answers describe Verlinde's formula for a modular tensor category, or a slight weakening of that condition.  Moore and Seiberg essentially proved the formula under the assumption that the sectors of a rational CFT form a modular tensor category (although I. Frenkel hadn't invented the name yet).  However, chiral CFTs are much richer objects than their categories of sectors, since they have correlation functions, OPEs and such.
One version of Verlinde's formula that is well-connected to chiral CFT is the following theorem of Huang (Theorem 5.5 in his paper):

Let $V$ be a simple rational $C_2$-cofinite vertex operator algebra of CFT type, with an invariant symmetric bilinear form, and let $Sect$ be the set of isomorphism classes of irreducible $V$-modules, equipped with duality involution $a \mapsto a'$.  Then $S_a^e \neq 0$ for all $a \in Sect$ (where $e$ represents $V$), and $$N_{a,b}^c = \sum_{d \in Sect} \frac{S_a^d S_b^d S_d^{c'}}{S_e^d}$$

Most of the conditions on $V$ are to ensure that there are finitely many modules, the modules have energy spectrum bounded below, and that they are completely reducible.  I don't know how essential the "simple" and "CFT type" are for the validity of the theorem, but they are reasonably natural.
There is almost no mention of the term "conformal blocks" in Huang's paper, but the fusion rules are described by the dimensions of spaces of intertwining operators.  By a 1994 theorem of Zhu, a space of intertwining operators is isomorphic to a space of 3-point genus zero conformal blocks (defined using a Lie algebra attached to a punctured Riemann sphere).
A: For those who are struggling getting started, let me add the following.
"Mathematical Aspects of the Verlinde Formula" M. Schottenloher (A Mathematical Introduction to Conformal Field Theory Lecture Notes in Physics Volume 759, 2008, pp 213-233).
He gives a proof of "abstract Verlinde rule" in a half-page and all definitions (quite simple)
in a half-page above. See section 11.4 page 229 lemma 11.13.
Well, of course, here is cheating in a sense: that to get usual Verlinde formulas one needs some extra work: "For the derivation of the Verlinde formula (Theorem 11.6) from the fusion rules using Lemma 11.13 we refer to [Sze95]... " 
Nevertheless, it might be worth mentioning this reference.
--
Added:
Another paper which discusses a variant of Verlinde formula using somewhat down-to-earch language is: 
Fourier transform and the Verlinde formula for the quantum double of a finite group T.H. Koornwinder, B.J. Schroers, J.K Slingerland, F.A. Bais
See page 12 theorem 5.3. Their formula is looks like the same as mentioned in the answer by Marcel and Scott. In their setup coeficients $N_{ab}^c$ describes certain fusion multiplication on the characters and matrix "S" is certain kind of Fourier transform.
--
Also let me remind this mathoverflow answer by B. Bartlett:
"
One nice fact, I think, is that the formula of Burnside that Geoff Robinson gives above,
$$
 N^{C_z}_{C_x C_y} = \frac{|G|}{|C_G(x)| |C_G(y)|} \frac{\chi(x) \chi(y) \chi(z^{-1})}{\chi(1)} 
$$
can be understood nicely from a geometric / topological quantum field theory perspective. I think it is precisely the "Verlinde formula" for the modular category Rep(/\G), the representation category of the Drinfeld double of C[G]... 
"
