How are oil and gas (hydrocarbons) formed?

Oil and gas (i.e. hydrocarbons, and all fossil fuels, including coal, for that matter) is made from the decomposition of organic material in an environment where there is limited oxygen.

With oil and gas the organic matter is mostly plankton and algae. These organic materials were deposited to the bottom of a body of water (the sea, or a lake) alongside sediments, which are small particles of inorganic material such as silt (which is very fine sand). Since there is a lack of oxygen in water, this organic matter and sediment doesn't decompose quickly, allowing thick accumulations to build up over thousands or millions of years.
Over millions of years, more and more sediments build up, forcing the organic material and sediments deeper and deeper, where the temperatures increase steadily (an increase of about 2.5 degrees C per kilometre is typical). This compaction causes the sediments to form into rocks. Provided those long-dead plankton and algae are not allowed to escape the compression and are subjected to high pressures and high temperatures for a long time (literally millions of years), then oil or gas will form.

Oil fact:

Hold a match to a fart and it will go up in a cloud of flame (and give you a painful burn up your backside as well).
This is methane combusting - the digestion of food in your stomach forms hydrocarbons, but only methane as it is the simplest one to make (cows release about 100 kg of methane a year - about the same pollution per day as a car - and this flatulence is a significant contributor to global warming).
If you could hold the food in your stomach under high pressure and high temperature for millions of years, you would crap nice, sweet crude, just like your favourite failed oil state.

It does not, however, accumulate in caverns or caves, like big tanks underground. Instead, it requires the rock to be porous, which means that there are gaps in between the tiny particles that form the rocks.
Often, the sediment that accumulates with the organic material forms rocks that aren't very porous (e.g. shale, or siltstone, which are formed from sedimentary clay and silt, respectively). The oil or gas is squeezed out, like water out of a sponge, and migrates. If there is nothing stopping it, it'll just leak away to the surface of the earth, and you won't get any great accumulation. This occurs naturally in many places around the world, and before the geology or chemistry behind oil formation was greatly understood this seepage gave a good indication of where to drill. The towers of Babylon were made in 4000 BC from asphalt (long chained, very viscous oil) taken from oil pits.

What you also need for oil and gas to be present is a reservoir, and a cap rock. The reservoir will be a rock that is both porous and permeable.
A porous rock, as has been mentioned, has porosity - it has gaps in its structure where oil or gas can reside. Permeability is when the gaps are such that this fluid can move freely throughout the rock. If it has porosity but no permeability there can be oil, but it will be very difficult to get out (though can be done by fracking).
Reservoirs are commonly sandstone (sand which has been deposited above the source rock and compacted into stone), though can be carbonate based (also formed from the dead - the calcium carbonate shells of crustaceans which have been again been deposited onto the seabed over millions of years), or any other rock formation which provides porosity and permeability. The cap rock will be above the reservoir. It has to be an impermeable rock so that the oil or gas doesn't just pass all the way through it to the surface - this could be shale which has been deposited on top of the sandstone, or more sandstone which just happens to be impermeable, or maybe it's dust from a volcanic eruption, or a thick bed of salt from a great salt lake.

Finally, you need a reservoir trap. The cap rock won't be completely flat (think of the sloping seabed, or the basin of a lake). If the cap rock is not completely flat then any hydrocarbons that are rising to the surface will just run along the underside of the cap rock until it escapes through the edges, or until it finds a place where it can accumulate - under the reservoir trap. This could be the shape of an inverted basin, or an upwards fold in the rock, or a whole number of things - again, these features are formed by the motion of the tectonic plates.

So we've established that you need organic matter under high pressure and high temperature for millions of years. You also need a porous rock to store the oil, which has to be permeable so that you can get it out when you've drilled it. Above this porous and permeable reservoir rock you need an impermeable cap rock which is in a shape that can accumulate oil and gas, so it doesn?t just go all the way to surface and seep away. That is quite a list of requirements, and you may wonder how such circumstances could have arisen so often to provide us with all the oil we use to build our roads, run our cars, make our plastic, generate our electricity, and contribute in general to our hydrocarbon dependency. Remember the time frame it takes to generate oil and gas - millions of years (70% of the world's oil comes from the Mesozoic era, which occurred 66 - 252 million years ago; another 15% comes from the Paleogene era, 23 - 66 million years ago).

Maybe from where you sit now the nearest place that could be a source for oil - a river estuary, a continental shelf - is hundreds of miles away. But in a few hundred thousand years several glaciers will maybe have come and gone (the last large glacial period, when most of northern Europe and Canada were covered in ice tens of metres thick, was only 15,000 years ago), and your town could be buried under a hundred metres of sediment at the bottom of a tropical lake. Add another hundred million years and there might be lake upon lake upon tropical forest upon desert upon sea where your house used to be, and the potential for all the requirements for an oil reservoir being somewhere in the thousands of feet of accumulated rock will be greatly increased.

So for oil and gas to form you need organic matter to be subject to high pressures and high temperatures for a very long time.