Ultrafast intraband carrier dynamics strongly influence many important characteristics in bulk and quantum well lasers and amplifiers through Spectral-Hole Burning (SHB) leading to nonlinear gain effects. In Quantum Dot (QD) devices, where the inter-level relaxation times can be even longer than the intraband relaxation times in conventional devices, SHB effects should also be substantial. A number of promising applications of QD amplifiers in high-speed optical processing (Cross-Gain Modulation, for instance) are based on features of the carrier dynamics in QD structures. In the present paper, based on a density matrix approach, we develop a theory of SHB-based nonlinear gain in QD lasers and amplifiers, which can affect such important characteristics as the modulation bandwidth in QD lasers and the saturation power and pulse energy in QD amplifiers. We give an expression for the nonlinear gain in QD devices, and show how it depends, particularly, on the capture/escape and relaxation/excitation rates.