Climate change, global warming, urban air pollution, energy supply uncertainty and depletion, and rising costs of conventional energy sources are, among others, potential socioeconomic threats that our community faces today. Transportation is one of the primary sectors contributing to oil consumption and global warming, and natural gas (NG) is considered to be a relatively clean transportation fuel that can significantly improve local air quality, reduce greenhouse-gas emissions, and decrease the energy dependency on oil sources. Internal combustion engines (ignited or compression) require only slight modifications for use with natural gas; rather, the main problem is the relatively short driving distance of natural-gas-powered vehicles due to the lack of an appropriate storage method for the gas, which has a low energy density. The U.S. Department of Energy (DOE) has set some targets for NG storage capacity to obtain a reasonable driving range in automotive applications, ruling out the option of storing methane at cryogenic temperatures. In recent years, both academia and industry have foreseen the storage of natural gas by adsorption (ANG) in porous materials, at relatively low pressures and ambient temperatures, as a solution to this difficult problem. This review presents recent developments in the search for novel porous materials with high methane storage capacities. Within this scenario, both carbon-based materials and metal-organic frameworks are considered to be the most promising materials for natural gas storage, as they exhibit properties such as large surface areas and micropore volumes, that favor a high adsorption capacity for natural gas. Recent advancements, technological issues, advantages, and drawbacks involved in natural gas storage in these two classes of materials are also summarized. Further, an overview of the recent developments and technical challenges in storing natural gas as hydrates in wetted porous carbon materials is also included. Finally, an analysis of design factors and technical issues that need to be considered before adapting vehicles to ANG technology is also presented.