Recent studies report the stiffness of coal changes, when exposed to sorbing gases such as CH4 and CO2. Although this effect might be potentially important for predicting the in situ mechanical behavior of coal seams during CH4 production or CO2 sequestration, very little understanding exists on the underlying mechanisms. In this paper, we report a single, long-duration mechanical test on a large, cube-shaped coal sample (Ruhr Basin, Germany). The sample was subjected to isostatic loading and unloading; first in the evacuated state (as received), and then each time after exposing it to pressurized, non-adsorbing He, or sorbing N2, CH4, and CO2. We find that exposure to sorbing gases led to swelling, which introduced a hysteresis in the stress-strain trajectory followed during mechanical loading. This hysteresis was almost absent in the evacuated state, and its magnitude depended strongly on the amount of adsorption-induced swelling exhibited by the sample. The apparent bulk modulus determined here for the CO2-equilibrated state was approximately 25% lower compared to the evacuated state. We qualitatively consider mechanisms that affect the elastic behavior of coal at the matrix and bulk scale, and argue that the observed effects are a combined effect of 1) changes in surface roughness at cleat interfaces and microfractures, and 2) a thermodynamic coupling between stress state, sorption capacity and swelling strain. The changes in stiffness relate to fluid-rock interaction effects, as well as to the presence of fractures, and hence not to the inherent elastic properties of the solid phase itself. We discuss the characteristics of each mechanism and the connection of the proposed mechanisms with formation-scale geomechanical effects of coal layers under conditions relevant to CBM/ECBM.