Removing shadows from document images can significantly improve the Quality of Experience (QoE) and boost the performance of the downstream document analysis and recognition tasks. However, existing methods still have limited generalization ability on complex document images and are prone to disrupt the image details. To address this issue, we consider the different shadow types that impact the image content on different frequency sub-bands. This motivates us to exploit frequency-domain information and further design a Frequency Information-oriented Deshadow Network (FID-Net). The proposed FID-Net mainly uses two elaborated modules, named Frequency Feature Extractor (FFE) and a Frequency Feature Refinement (FFR). FFE can generate low/high-frequency features through adaptively decomposing spectra of the shadow image. After that, FFR further refines both frequency features with mutual information operations. With the proposed key designs, extensive experimental results on the commonly used benchmarks demonstrate that the proposed method can learn discriminative shadows and achieve favorable performance against state-of-the-art approaches.