A leap year (or intercalary year) is a year containing an extra day or month in order to keep the calendar year in sync with an astronomical or seasonal year. Seasons and astronomical events do not repeat at an exact number of days, so a calendar which had the same number of days in each year would over time drift with respect to the event it was supposed to track. By occasionally inserting (or intercalating) an additional day or month into the year, the drift can be corrected.
Leap years (which keep the calendar in sync with the year) should not be confused with leap seconds (which keep clock time in sync with the day).
Gregorian calendar
The Gregorian calendar adds an extra day to February, making it 29 days long, in years where the quotient has no remainder when divided by 4, excluding years where the quotient has no remainder when divided by 100, but including years where the quotient has no remainder when divided by 400. So 1996, 2000, and 2400 are leap years but 1899, 1900 and 2100 are not.
The reasoning behind this rule is as follows:
 The Gregorian calendar is designed to keep the vernal equinox on or close to March 21, so that the date of Easter (celebrated on the Sunday after the 14th day of the Moon that falls on or after March 21) remains correct with respect to the vernal equinox.
 The vernal equinox year is currently about 365.242375 days long.
 The Gregorian leap year rule gives an average year length of 365.2425 days.
This difference of a little over 0.0001 days means that an error of a day will accumulate in around 8,000 years. But in 8,000 years' time the length of the vernal equinox year will have changed by an amount we can't accurately predict (see below). So the Gregorian leap year rule does a good enough job.
Which day is the leap day?
The Gregorian calendar is a modification of the Julian calendar first used by the Romans. The Roman calendar originated as a lunar calendar (though from the 5th century BC it no longer followed the real moon) and named its days after three of the phases of the moon: the new moon (calends, hence "calendar"), the first quarter (nones) and the full moon (ides). Days were counted down (inclusively) to the next named day, so 24 February was ante diem sextum calendas martii ("the sixth day before the calends of March").
Since 45 BC, February in a leap year had two days called "the sixth day before the calends of March". The extra day was originally the second of these, but since the third century it was the first. Hence the term bissextile day for 24 February in a bissextile year.
Where this custom is followed, anniversaries after the inserted day are moved in leap years. For example, the former feast day of Saint Matthias, 24 February in ordinary years, would be 25 February in leap years.
This historical nicety is, however, in the process of being discarded: The European Union declared that, starting in 2000, 29 February rather than 24 February would be leap day, and the Roman Catholic Church also now uses 29 February as leap day. The only tangible difference is felt in countries which celebrate 'name days'.
Julian calendar
The Julian calendar adds an extra day to February in years divisible by 4.
This rule gives an average year length of 365.25 days. The excess of about 0.0076 days with respect to the vernal equinox year means that the vernal equinox moves a day earlier in the calendar every 130 years or so.
Revised Julian Calendar
The Revised Julian calendar adds an extra day to February in years divisible by 4, except for years divisible by 100 that do not leave a remainder of 200 or 600 when divided by 900.
This rule agrees with the rule for the Gregorian calendar until 2800 (a leap year in the Gregorian calendar but not in the Revised Julian calendar).
This rule gives an average year length of 365.242222… days. This is a very good approximation to the mean tropical year, but because the vernal equinox tropical year is slightly longer, the Revised Julian calendar does not do as good a job as the Gregorian calendar of keeping the vernal equinox on or close to March 21.
Chinese calendar
The Chinese calendar is lunisolar, so a leap year has an extra month, often called an embolismic month after the Greek word for it. In the Chinese calendar the leap month is added according to a complicated rule, which ensures that month 11 is always the month that contains the northern winter solstice. The intercalary month takes the same number as the preceding month; for example, if it follows the second month then it is simply called "leap second month".
Hebrew calendar
The Hebrew calendar is also lunisolar with an embolistic month. In the Hebrew calendar the extra month is called Adar Alef (first Adar) and is added before Adar, which then becomes Adar Sheni (second Adar). According to the Metonic cycle, this is done seven times every nineteen years, specifically, in years, 3, 6, 8, 11, 14, 17, and 19.
In addition, the Hebrew calendar has postponement rules that postpone the start of the year by one or two days. The year before the postponement gets one or two extra days, and the year whose start is postponed loses one or two days. These postponement rules reduce the number of different combinations of year length and starting day of the week from 28 to 14, and regulate the location of certain religious holidays in relation to the Sabbath.
Hindu Calendar
In the Hindu calendar which is lunisolar calendar, embolistic month called adhika maas (extra month) is added when the lunar year went about 30 days behind the solar calendar. A number of regions still use the purely lunar calendar, but the intercalary is determined as the month in which the sun is in the same zodiac on two consecutive dark moons.
Iranian calendar
The Iranian calendar also has a single intercalated day once in every four years, but every 33 years or so the leap years will be five years apart instead of four years apart. The system used is more accurate and more complicated, and is based on the time of the March equinox as observed from Teheran. The 33year period is not completely regular; every so often the 33year cycle will be broken by a cycle of 29 or 37 years.
Long term leap year rules
The accumulated difference between the Gregorian calendar and the vernal equinoctial year amounts to 1 day in about 8,000 years. This suggests that the calendar needs to be improved by another refinement to the leap year rule: perhaps by avoiding leap years in years divisible by 8,000.
(The most common such proposal is to avoid leap years in years divisible by 4,000 [1]. This is based on the difference between the Gregorian calendar and the mean tropical year. Others claim, erroneously, that the Gregorian calendar itself already contains a refinement of this kind [2], [3].)
However, there is little point in planning a calendar so far ahead because over a timescale of tens of thousands of years the number of days in a year will change for a number of reasons, most notably:

Precession of the equinoxes moves the position of the vernal equinox with respect to perihelion and so changes the length of the vernal equinoctial year.

Tidal acceleration from the sun and moon slows the revolution of the earth, making the day longer.
In particular, the second component of change depends on such things as postglacial rebound and sea level rise due to climate change. We can't predict these changes accurately enough to be able to make a calendar that will be accurate to a day in tens of thousands of years.
Number of leap years starting on a given day of the week
Because there are 97 leap years in every 400 in the Gregorian Calendar, there should, in each "cycle", be either 13 or 14 leap years starting on each day of the week. However, the effects of the "common" centennial years (1700, 1800, 1900, 2100, 2200 etc.) cause major alterations.
This is because the absence of an extra day in such years causes the following leap year (1704, 1804, 1904, 2104 etc.) to start on the same day of the week as the leap year twelve years before (1692, 1792, 1892, 2092 etc.). Similarly, the leap year eight years after a "common" centennial year (1708, 1808, 1908, 2108 etc.) starts on the same day of the week as the leap year immediately prior to the "common" centennial year (1696, 1796, 1896, 2096 etc.). Thus, those days of the week on which such leap years begin gain an extra year or two in each cycle. In each cycle there are:
Marriage proposal
There is a tradition, said to go back to Saint Patrick and Saint Bridget in 5th century Ireland, whereby women could only make marriage proposals in leap years.
Saint Patrick and the leap year
 Saint Patrick, having driven the frogs out of the bogs was walking along the shores of Lough Neagh, when he was accosted by Saint Bridget in tears, and was told that a mutiny had broken out in the nunnery over which she presided, the ladies claiming the right of popping the question.
 Saint Patrick said he would concede them the right every seventh year, when Saint Bridget threw her arms round his neck, and exclaimed, "Arrah, Pathrick, jewel, I daurn't go back to the girls wid such a proposal. Make it one year in four." Saint Patrick replied, "Bridget, acushla, squeeze me that way again, an' I'll give ye leapyear, the longest of the lot." Saint Bridget, upon this, popped the question to St Patrick himself, who, of course, could not marry: so he patched up the difficulty as best he could with a kiss and a silk gown.
(Source: Evans, Ivor H, Brewer's Dictionary of Phrase and Fable, Cassell, London, 1988)
According to a 1288 law in Scotland, fines were levied if the proposal was refused by the man; compensation ranged from a kiss to a silk gown to soften the blow. Because men felt that put them at too great a risk, the tradition was in some places tightened to restricting female proposals to 29 February.