The effect of trimethylamine-N-oxide (TMAO) on hydrophobic solvation and hydrophobic interactions of methane has been studied with Molecular Dynamics simulations in the temperature range between 280 and 370 K at 1 bar ambient pressure. We observe a temperature transition in the effect of TMAO on the aqueous solubility of methane. At low temperature (280 K), methane is preferentially hydrated, causing TMAO to reduce its solubility in water, while above 320 K, methane preferentially interacts with TMAO, causing TMAO to promote its solubility in water. Based on a statistical-mechanical analysis of the excess chemical potential of methane, we find that the reversible work of creating a repulsive methane cavity opposes the solubility of methane in TMAO/water solution more than in pure water. Below 320 K, this solvent-excluded volume effect overcompensates the contribution of methane-TMAO van der Waals interactions, which promote the solvation of methane and are observed at all temperatures. These van der Waals interactions with the methyl groups of TMAO tip the balance above 320 K where the effect of TMAO on solvent-excluded volume is smaller. We furthermore find that the effective attraction between dissolved methane solutes increases with the increasing TMAO concentration. This observation correlates with a reduction in the methane solubility below 320 K but with an increase in methane solubility at higher temperatures.