Literally means "All vows". It is the prayer that introduces the evening service in the Synagogue on Yom Kippur, the holiest day in the Jewish year. The term is also used to refer to the whole service.
Everybody who can comes to Synagogue before dark, with only usually young children (and mothers looking after them) not attending. Men wear a Tallit - the only time it is worn in the evening. It is often the time the Synagogue is busiest in the whole year with many synagogues opening up extensions or running parallel services to accommodate everybody (many Jews only come to Synagogue on Rosh Hashanah and Yom Kippur, so making the main building big enough for everybody would make it empty 99% of the time).
Two Torahs are taken out of the ark (in some Synagogues they are all taken out and walked round the synagogue for members of the congregation to kiss, and then all but two are returned). The Chazzan stands between the two people holding them, the three of them forming an ad hoc Beth Din.
The Chazzan starts by reciting a short passage which says "With the permission of the (one who is) above (ie G-D), and with the permission of the (ones who are) below (ie us), with the knowledge of G-D, and with the knowledge of the congregation, we are permitted to pray with the sinners". This is because sinners may have been excluded from communal prayer throughout the year - at this time, they are welcomed back to repent.
Then, the Kol Nidrei prayer starts. The exact order of the words can vary slightly from congretation to congregation, according to different traditions, but the key parts are all the same. The tune is almost universal and was made famous in the Neil Diamond version of the film The Jazz Singer. As the Chazzan sings it, the congregation say it quietly together.
All vows, prohibitions, oaths, consecrations, konam-vows (*), konas-vows (*), or equivalent terms that we may vow, swear, consecrate, or prohibit upon ourselves - (from the last Yom Kippur until this Yom Kippur, and) from this Yom Kippur until the next Yom Kippur, may it come upon us for good - regarding them all, we regret them henceforth. They all will be permitted, abandoned, cancelled, null and void, without power and without standing. Our vows shall not be valid vows; our prohibitions shall not be valid prohibitions; and our oaths shall not be valid oaths.
(*) konam-vows and konas-vows were specific types of vows made in Temple times.
This prayer has been used as a source of anti-semitism over the years. People would say "don't ever lend money to a Jew, he makes this prayer once a year and things he has no obligation to pay it back". To refute this argument, we have to look at the origins of the prayer.
The Kol Nidrei prayer dates back to The Spanish Inquisition, where Jews were forced to convert to Christianity or be killed. Many of the Jews outwardly converted, but then once a year said this prayer to reconcile themselves before G-D. For that matter, the whole of Yom Kippur is only to atone for sins against G-D - if you have sinned against another man, you have to personally ask him for forgiveness.
The Kol Nidrei service then proceeds like any other evening service, with the Shema and Amidah. However, there are then Selichot, the only time in the year the evening service is extended like this. Selichot are prayers for forgiveness, and many are only said this one time in the year. They are all communal prayers, sung together, and separated with the 13 divine attributes of G-D.
Merciful G-D, merciful G-D, powerful G-D, compassionate and gracious, slow to anger, and abundant in kindness and truth. Preserver of kindness for thousands of generations, forgiver of iniquity, willful sin and error, and Who cleanses. (Exodus 34:6-7)
This was the prayer G-D taught to Moses after the Children of Israel committed the sin of the Golden Calf. Therefore it is an appropriate prayer to say on the Day of Atonement, and hence it features throughout the whole day's prayers.