To add to Mark H's answer, I'd like to flesh out Emilio Pisanty's comment a bit more:
Doppler shifts contribute, but there are multiple ways to make them disappear. However, homogeneous broadening - particularly liftetime broadening, caused by the fact that even if the laser pulse is long, each atom still decays within a finite time - is the ultimate lower limit on the bandwidth.
as I think a few equations with an intuitive overview of homogeneous broadening may help here. As further talked about in my answer here, the Schrödinger equation for the evolution of the Schrödinger-picture quantum state of a system comprising a lone stimulated atom coupled to the electromagnetic field can be reduced to three coupled differential equations:
$$\begin{array}{lcl}
i\,\mathrm{d}_t\, \psi_0(t) &=& \omega_0 \,\psi_0(t) + \int_0^\infty \left(\kappa_+(\omega)^* \,\psi_+(\omega, t)+\kappa_-(\omega)^* \,\psi_-(\omega, t)\right)\, \mathrm{d}\omega\\
i\,\partial_t \,\psi_\pm(\omega, t) &=& \omega\, \psi_\pm(\omega, t) + \kappa_\pm(\omega) \,\psi_0(t)\end{array}\tag{1}$$
where $\psi_0(t)$ is the probability amplitude of the emitter atom's being excited together with the continuous functions $\psi_\pm(\omega)$ which are the probability amplitude densitites to find the photon in one of the (in general degenerate) modes with frequency $\omega$ and in left and right hand circular polarization ($\pm$ standing for left and right handed polarization, respectively).
As I show in my other answer, as long as the coupling $\kappa_\pm(\omega)$ is broadband, these equations approximately (see plot and equation (2) and discussion thereafter) reproduce the memoryless decay of a spontaneously emitting atom with probability density $p(t) = \frac{1}{\tau}\exp\left(-\frac{t}{\tau}\right)$ of time till decay given by the exponential distribution, where the mean time till decay ${\rm{\tau}}
\approx
\left.
{
\frac{1}{
{\rm{2}}\,{\rm{\pi}}\,\,
\left(
{
{\rm{\kappa}}_+^2+
{\rm{\kappa}}_-^2
}
\right)
}
}
\right|_{{\rm{\omega}}={\rm{\omega}}_{\rm{0}}}$ is inversely proportional to the magnitude squared of the cross-coupling strength $\kappa_\pm(\omega_0)$.
It's very helpful (or at least I find it so) to put into everyday words what all these equations are telling us. The atom is coupled to all modes roughly equally. However, it cannot emit into all equally, because if it couples to a frequency significantly away from $\omega_0$, destructive interference hinders the process. So only frequencies near $\omega_0$ are excited. But the weaker the coupling, the less the hindering of this process by destructive interference, hence a broader frequency spread. The behavior of Eq. (1) under broadband assumptions implies a Lorentzian lineshape in the frequency domain, thus we can understand the mechanisms behind the most common spontaneous emission lineshape.
A plot of this process is shown below:
This plot shows the probability amplitude:
$$\psi_+(\omega,\,t)\approx i \sqrt{\frac{2\,\tau}{\pi}} \,e^{-i\, t\, \omega }\, \frac{1-\exp\left(-t\,\left(\frac{1}{2\, \tau }+i\,\omega_0\right)\right)}{2 \,\tau \, (\omega -\omega_0)+i}\tag{2}$$
for the photon to be found in an EM field mode with frequency $\omega$ (nearly transverse axis) against time $t$ (axis moving away from viewer). The atom transition energy is such that $\omega_0 = 1$ on this plot, and the transverse axis stretches from $\omega=0$ (left) to $\omega=2$ (right). The relaxation tim $\tau=10$ and the time axis stretches from $t=0$ to $t=100$. The magnitude is encoded as the vertical axis, the phase as hue. It can be seen that at small times, the probability amplitude is spread over a very wide frequency band, but, owing to the destructive interference mentioned, concentrates itself around the center frequency as $t\to\infty$, such that the probability density becomes a Lorentzian function of frequency.
Take heed that one of the approximations used to derive (2) is that the frequency $\omega_0$ is high enough and the coupling $\kappa_\pm(\omega)$ not so wide that the integration in (1) over the positive frequency axis $\omega\in[0,\,\infty)$ can be approximated as an integral over the whole real line. Indeed, we cannot reproduce the memoryless exponential distribution if we do not make this approximation and truncate the integral as in (1).
For this reason, it is impossible for quantum decays to be exactly memoryless, a fact that has been experimentally observed as discussed in Akmetali's Answer here.
Lastly, let's look at the values of Lorentzian linewidth attributable to this effect alone. $\tau$ is most often of the order of a nanosecond, as I discuss here, which implies a linewidth of $100{\rm MHz}$, equivalent to about $10^{-4}$ of a nanometer linewidth. The resonant cavity further narrows this linewidth by the phenomenon of Purcell Enhancement (I further discuss this in the latter part of my other answer); one hundredfold narrower linewidths are therefore not uncommon in lasers.
