Theory of the generation linewidth of a current-driven spin-torque magnetic nano-oscillator in the presence of thermal fluctuations has been developed and a simple analytical formula for the generation linewidth in the supercritical regime of generation has been derived. It is shown that the strong dependence of the oscillator frequency on the precession power leads to substantial broadening of the generation linewidth of a spin-torque oscillator compared to the case of a linear oscillator, i.e. an oscillator with power-independent generation frequency. The relation between the nonlinearity-induced broadening of the generation linewidth and the nonlinearity-induced increase of the phase-locking band of a spin-torque oscillator to an external microwave signal has been revealed. The derived expression for the generation linewidth predicts a linewidth minimum when the nano-contact is magnetized at a certain angle to its plane, at which the nonlinear frequency shift vanishes. This result is in good agreement with recent experiments.