A Tesla Coil is an aircored resonant transformer. It has some similarities with a standard transformer but the mode of operation is somewhat different. A standard transformer uses tight coupling between its primary and secondary windings and the voltage transformation ratio is due to turns ratio alone. In contrast, a Tesla Coil uses a relatively loose coupling between primary and secondary, and the majority of the voltage gain is due to resonance rather than the turns ratio. A normal transformer uses an iron core in order to operate at low frequencies, whereas the Tesla Coil is aircored to operate efficiently at much higher frequencies.
A typical Tesla Coil circuit diagram is shown below.
The operation of the Tesla Coil is as follows:
During the damped primary oscillation energy passes back and forth between the primary capacitor and the primary inductor. Energy is stored alternately as voltage across the capacitor or current through the inductor. Some of the energy from the capacitor also produces considerable heat and light in the spark gap. Energy dissipated in the spark gap is energy which is lost from the primary tank circuit, and it is this energy loss which causes the primary oscillation to decay relatively quickly with time.
I like this spiral diagram because I think it shows how the voltage and current are 90 degrees out of phase. The distance of the dot from the origin represents the amount of energy in the system as the oscillation decays. It also reminds me of a primary coil shape ! 
The close proximity of the primary and secondary windings causes magnetic coupling between them. The high amplitude oscillating current flowing in the primary causes a similar oscillating current to be induced in the nearby secondary coil.
"Primary Ringdown" to first primary notch 

"Secondary Ringup" to first maximum 
Eventually all of the energy has been transferred to the secondary system and none is left in the primary circuit. This point is known as the "First primary notch" because the amplitude of the primary oscillation has fallen to zero. It is the first notch because the energy transfer process usually does not stop here. In an ideal system the spark gap would cease to conduct at this point, when all of the energy is trapped in the secondary circuit. Unfortunately, this rarely happens in practice.
In the animation opposite the front pendulum represents the primary voltage and the rear pendulum represents the secondary voltage. Notice how the amplitude of each pendulum changes as energy is transferred back and forth from one to the other. A mechanical model such as this can easily be built and provides a good analogy to the electrical case. It really does work ! The "notches" are clearly visible when one pendulum appears to momentarily stop. 
Secondary Ringdown after spark gap stops conducting 
It should be noted that this repeating process is an important mechanism for the generation of long sparks. This is because successive sparks build on the hot ionised channels formed by previous sparks. This allows sparks to grow in length over several firings of the system. In practice the whole process described above may take place several hundred times per second.
But how does the Tesla Coil produce such a massive secondary voltage ?
Now for the maths bit…
The terrific voltage gain of the Tesla Coil comes from the fact that the energy in the large primary tank capacitor is transferred to the comparatively small stray capacitance of the secondary circuit. The energy stored in the primary capacitor is measured in Joules and is found from the following formula:
Ep = 0.5 Cp Vp²
If, for example, the primary capacitor is 47nF and it is charged to 20kV then the stored energy can be calculated.
Ep = 0.5 x 47n x (20000)² = 9.4 Joules
If we assume there are no losses in the transfer of energy to the secondary winding, the theory of conservation of energy states that this energy will be transferred to the secondary capacitance Cs. Cs is typically around 25pF. If it contains 9.4 Joules of energy when the energy transfer is complete, we can calculate the voltage:
Es = 0.5 x 25p x Vs² = 9.4
Vs² = 9.4 / (0.5 x 25p)
Vs = 867 kV
The theoretical voltage gain of the Tesla Coil is actually equal to the square root of the Capacitance ratio.
Gain = sqrt (Cp / Cs)
The voltage gain can also be calculated in terms of the inductances…
For the Tesla Coil to work, the resonant Frequencies of the Primary circuit and the Secondary circuit must be identical. I.e. Fp must equal Fs.
Fp = 1 / 2 pi sqrt (LpCp) = Fs = 1 / 2 pi sqrt (LsCs)
Therefore: LpCp = LsCs
The ratio of the inductances is the inverse of the ratio of the capacitances, and therefore the voltage gain is as follows:
Gain = sqrt (Ls / Lp)
All of the above equations calculate the theoretical maximum voltage gain. In practice the voltage at the top of the secondary will never get quite this high because of several factors:
The above equations assume that all of the energy from the primary capacitor makes the journey into the secondary capacitor. In practice some energy is lost due to resistance of the windings of both coils.
A significant proportion of the initial energy is lost as light, heat, and sound in the primary spark gap.
The primary and secondary coils act like antennas and radiate a small amount of energy in the form of radio waves.
The waveform opposite shows how the secondary voltage drops drastically when an arc forms between the toroid and a nearby grounded object. This is an approximate representation of a real waveform observed whilst a running coil discharged to an earthed target 12 inches away. The secondary voltage rises to around 300kV in only 3 cycles, This is sufficient to breakdown the 12 inch gap, and the arc which is formed loads the secondary reducing the voltage. 
The size of the Toroid (or discharge terminal) is very important. If it is small, it will theoretically result in a higher secondary voltage due to its lower capacitance (Cs). However, in practice its small radius of curvature will cause the surrounding air to breakdown prematurely at a low voltage before the maximum level is reached. A large toroid theoretically results in a lower peak secondary voltage (due to more Cs) but in practice gives good results because its larger radius of curvature delays the breakdown of the surrounding air until a higher voltage is reached.
It is possible to fit a very large toroid to a Tesla Coil which actually prevents the surrounding air from breaking down. In this instance no power is dissipated in the form of secondary sparks, and energy from the tank capacitor is dissipated between the spark gap, stray resistances, and RF radiation.
More theory of operation
Click here for the next section on Quenching, Coupling and Frequency Splitting.