We find that the sheath regions between fast interplanetary coronal mass ejections (ICMEs) and their preceding shocks are often characterized by plasma depletion and mirror wave structures, analogous to planetary magnetosheaths. A case study of these signatures in the sheath of a magnetic cloud (MC) shows that a plasma depletion layer (PDL) coincides with magnetic field draping around the MC. In the same event, we observe an enhanced thermal anisotropy and plasma beta as well as anticorrelated density and magnetic fluctuations which are signatures of mirror mode waves. We perform a superposed epoch analysis of ACE and Wind plasma and magnetic field data from different classes of ICMEs to illuminate the general properties of these regions. For MCs preceded by shocks, the sheaths have a PDL with an average duration of 6 hours (corresponding to a spatial span of about 0.07 AU) and a proton temperature anisotropy T$perp$p/T$parallel$p $simeq$ 1.2--1.3, and are marginally unstable to the mirror instability. For ICMEs with preceding shocks which are not MCs, plasma depletion and mirror waves are also present but at a reduced level. ICMEs without shocks are not associated with these features. The differences between the three ICME categories imply that these features depend on the ICME geometry and the extent of upstream solar wind compression by the ICMEs. We discuss the implications of these features for a variety of crucial physical processes including magnetic reconnection, formation of magnetic holes, and energetic particle modulation in the solar wind.