Amplitude modulation of the broadband propeller noise as a result of the cavitation yields a second-order cyclostationary ship-radiated noise. The spectrum of the modulating signal, consisting of the so-called propeller (or cavitation) tonals, enables the detection and the classification of the submarines or surface ships. However, data acquisition for this purpose causes vast data sizes due to high sampling rates and multiple sensor deployment. To mitigate the negative effects of this acquisition process such as on energy efficiency, hardware complexity, and storage capacity, we propose a scheme for compressive sensing of propeller tonals. We show that the spectral correlation function of cyclastationary propeller noise is sparse and derive a linear relationship between the compressive and Nyquist-rate cyclic modulation spectra, i.e., the approximation of spectral correlation function that allows utilizing matrix representations required in compressive sensing. It also enables use of the cyclic modulation coherence, i.e., the normalized cyclic modulation spectrum, to demonstrate the effect of compressive sensing in terms of statistical detection. We compare the recovery and detection performance results of the sparse approximation algorithms based on the so-called iterative hard thresholding and compressive sampling matching pursuit. Results show that compression is achievable without affecting the detection performance negatively. The main challenges are the weak modulation, low signal-to-noise ratio, and nonstationarity of the ambient noise, all of which reduce the sparsity level, hence causing degraded recovery and detection performance.