Monte Carlo and molecular dynamics simulations were performed to investigate the effect on the solubility, diffusion, and permeability of water and oxygen when adding graphene or single-walled carbon nanotubes (SWCNTs) to polyethylene (PE). When compared with pure PE, addition of graphene lowered the solubility of water, whereas at lower temperatures, the oxygen solubility increased because of the oxygen–graphene interaction. Addition of SWCNTs lowered the solubility of both water and oxygen when compared with pure PE. A detailed analysis showed that an ordered structure of PE is induced near the additive surface, which leads to a decrease in the diffusion coefficient of both penetrants in this region. The addition of graphene does not change the permeation coefficient of oxygen (in the direction parallel to the filler) and, in fact, may even increase this coefficient when compared with pure PE. In contrast, the water permeability is decreased when graphene is added to PE. The addition of SWCNTs decreases the permeability of both penetrants. Graphene can consequently be added to selectively increase the solubility and permeation of oxygen over water, at least at lower temperatures.