Gas hydrates are also possible and are now known to be extremely common in the depths of oceans as well as occurring in permafrost. The gas hydrate occurs when the loosely bound water forms a crystal like structure that is bonded to methane. The crystal is ice-like due to the pressure that deep ocean water applies on the chemicals. This article from Popular Mechanics provides a simple yet comprehensive explanation of Methane Hydrates: http://www.popularmechanics.com/science/earth/2558946.html
On the second page of the Popular Mechanics article the following data is provided by the US Geological Survey: Somewhere between 100,000 and 3 million trillion cubic feet of methane exists in hydrate form on planet earth. For comparison the US consumes approximately 23 trillion cubic feet a year of methane for home and business heating, industry, and electricity generation. The world uses about 90 trillion cubic feet a year of methane. Therefore there are between 1,100 and 33,000 years of the global usage of methane gas trapped as hydrates. That is the good news. Now we hear the bad news. Extracting the methane from the hydrates is not simple and will require the engineering of systems that lower the pressure applied by the deep ocean. Also we do not want to inadvertently release copious amounts of methane as this gas has 21 times the global warming effect on a pound for pound basis versus carbon dioxide.
In fact there is a scare regarding the uncontrolled release of methane from hydrates that are trapped below permafrost. In this case, the hydrate forms because of low temperature rather than high pressure. Thermodynamically one can think about the equilibrium of solids and gases kind of like the way dry ice sublimes. As dry ice warms the solid becomes gaseous. To prevent dry ice from subliming one can either keep it very cold or store it under high pressure so that the conditions favor it remaining a solid. Similarly methane hydrates will remain in the hydrated condition if the pressure remains high (under the sea) or the in the case of permafrost the temperature remains very cold. I have no doubt that after we have exhausted the conventional methane sources in about fifty years in the future we will engineer systems to recover methane from hydrates. The company that commercializes the process will dwarf Exxon Mobil and Shell.