Graphene oxide (GO) sheets exhibit superior adsorption capacity for removing organic dye pollutants from an aqueous environment. In this paper, the facile preparation of GO/polyethylenimine (PEI) hydrogels as efficient dye adsorbents has been reported. The GO/PEI hydrogels were achieved through both hydrogen bonding and electrostatic interactions between amine-rich PEI and GO sheets. For both methylene blue (MB) and rhodamine B (RhB), the as-prepared hydrogels exhibit removal rates within about 4 h in accordance with the pseudo-second-order model. The dye adsorption capacity of the hydrogel is mainly attributed to the GO sheets, whereas the PEI was incorporated to facilitate the gelation process of GO sheets. More importantly, the dye-adsorbed hydrogels can be conveniently separated from an aqueous environment, suggesting potential large-scale applications of the GO-based hydrogels for organic dye removal and wastewater treatment.