Magnetic carbon nanomaterials have been widely adopted as adsorbents in water treatment, but the low adsorption capacities largely limit their practical applications. In this study, magnetic graphene sponge (Fe3O4-GS) was prepared by lyophilization for the adsorption of dye pollutant. The incorporation of Fe3O4 enabled the magnetic separation of Fe3O4-GS after the adsorption of methylene blue (MB). The adsorption capacity of Fe3O4-GS for MB was 526 mg/g, much higher than those of the magnetic carbon nanoadsorbents in the literature. The adsorption kinetics of MB on Fe3O4-GS was moderately fast, which could be analyzed by the pseudo-second-order model and intraparticle diffusion model. The thermodynamics study revealed that the adsorption was driven by the increased randomness on the interface. The pH and ionic strength had meaningful influences on the adsorption capacity of Fe3O4-GS. The facile regeneration of Fe3O4-GS would definitely reduce its operating cost. The implications to the environmental applications of magnetic carbon nanoadsorbents are discussed.