Due to the fact that invalid cloud-covered regions in remote sensing images consume a considerable quantity of coding bit rates under the limited satellite-to-ground transmission rate, existing image compression methods suffer from low compression efficiency and poor reconstruction quality, especially in cloud-free regions which are generally regarded as regions of interest (ROIs). Therefore, we propose an efficient on-board compression method for remote sensing images with arbitrary-shaped clouds by leveraging the characteristics of cloudy images. Firstly, we introduce two novel spatial preprocessing strategies, namely, the optimized adaptive filling (OAF) strategy and the controllable quantization (CQ) strategy. Specifically, the OAF strategy fills each cloudy region using the contextual information at its inner and outer edge to completely remove the information of cloudy regions and minimize their coding consumption, which is suitable for images with only thick clouds. The CQ strategy implicitly identifies thin and thick clouds and rationally quantifies the data in cloudy regions to alleviate information loss in thin cloud-covered regions, which can achieve the balance between coding efficiency and reconstructed image quality and is more suitable for images containing thin clouds. Secondly, we develop an efficient coding method for a binary cloud mask to effectively save the bit rate of the side information. Our method provides the flexibility for users to choose the desired preprocessing strategy as needed and can be embedded into existing compression framework such as JPEG2000. Experimental results on the GF-1 dataset show that our method effectively reduces the coding consumption of invalid cloud-covered regions and significantly improve the compression efficiency as well as the quality of decoded images.