We present a discrete element model for simulating, at the grain scale, gas migration in brine-saturated deformable media. We rigorously account for the presence of two fluids in the pore space by incorporating forces on grains due to pore fluid pressures and surface tension between fluids. This model, which couples multiphase fluid flow with sediment mechanics, permits investigation of the upward migration of gas through a brine-filled sediment column. We elucidate the ways in which gas migration may take place: (1) by capillary invasion in a rigid-like medium and (2) by initiation and propagation of a fracture. We find that grain size is the main factor controlling the mode of gas transport in the sediment, and we show that coarse-grain sediments favor capillary invasion, whereas fracturing dominates in fine-grain media. The results have important implications for understanding vent sites and pockmarks in the ocean floor, deep subseabed storage of carbon dioxide, and gas hydrate accumulations in ocean sediments and permafrost regions. Our results predict that in fine sediments, hydrate will likely form in veins following a fracture network pattern, and the hydrate concentration will likely be quite low. In coarse sediments, the buoyant methane gas is likely to invade the pore space more uniformly, in a process akin to invasion percolation, and the overall pore occupancy is likely to be much higher than for a fracture-dominated regime. These implications are consistent with laboratory experiments and field observations of methane hydrates in natural systems.