Owing to the complexity of the ocean background noise, underwater acoustic signal denoising is one of the hotspot problems in the field of underwater acoustic signal processing. In this paper, we propose a new technique for underwater acoustic signal denoising based on complete ensemble empirical mode decomposition with adaptive noise (CEEMDAN), mutual information (MI), permutation entropy (PE), and wavelet threshold denoising. CEEMDAN is an improved algorithm of empirical mode decomposition (EMD) and ensemble EMD (EEMD). First, CEEMDAN is employed to decompose noisy signals into many intrinsic mode functions (IMFs). IMFs can be divided into three parts: noise IMFs, noise-dominant IMFs, and real IMFs. Then, the noise IMFs can be identified on the basis of MIs of adjacent IMFs; the other two parts of IMFs can be distinguished based on the values of PE. Finally, noise IMFs were removed, and wavelet threshold denoising is applied to noise-dominant IMFs; we can obtain the final denoised signal by combining real IMFs and denoised noise-dominant IMFs. Simulation experiments were conducted by using simulated data, chaotic signals, and real underwater acoustic signals; the proposed denoising technique performs better than other existing denoising techniques, which is beneficial to the feature extraction of underwater acoustic signal.