Registers of the Church of Scotland prior to 1855 are held at the National Records of Scotland in Edinburgh (see also the GRO tutorial). Copies can also be seen at LDS family history centres around the world.
Church of Scotland records after that date, as well as records of a number of non-conformist churches (e.g. Catholic, Episcopalian, Free Church) are usually held at the National Records of Scotland in Edinburgh.
Baptisms and marriages in the Church of Scotland parish registers before 1855 have been indexed and these indexes may be consulted at the National Records of Scotland in Edinburgh, in LDS family history centres around the world , and also online through ScotlandsPeople, which also provides digitised images of records (for a fee).
Old Parish Registers of Baptisms, Marriages and Burials, 1553-1854 can be consulted as digital images, either by visiting the ScotlandsPeople Centre in Edinburgh or through the pay-per-view website ScotlandsPeople.
List of the Old Parochial Registers. This list is based on the printed Detailed List of the Old Parochial Registers of Scotland which was first published in 1872. It provides a basic reference guide for identifying the dates for the births/baptisms, marriages/proclamations of marriage and deaths/burials in the Old Parish Registers (OPRs) held by the National Records of Scotland. Three appendices are also provided which list: (1) Church of Scotland records in the National Records of Scotland (formerly the Scottish Record Office and the National Archives of Scotland) containing pre-1855 birth, death and marriage entries. (2) Kirk session and other material found in the OPRs. (3) Miscellaneous records containing entries from Non-Conformist churches relevant to the OPRs. For a printed guide to the above see The Parishes, Registers & Registrars of Scotland edited by S.M. Spiers and published by the Scottish Association of Family History Societies. This also contains parish maps for each county and a list of addresses for local Register Offices (see also the Civil Registration section).
The Kirk Session of a parish consists of the minister of the parish and the elders of the congregation. It looks after the general wellbeing of the congregation and, particularly in centuries past, parochial discipline. Most Kirk Session records are held in the National Records of Scotland in Edinburgh and can be fascinating. For more information on this see Anne Gordon's Candie for the Foundling published by the Pentland Press in 1992. ISBN 1 872795 75 7 (720 pages).
To assist in the identification of the different entities that have existed during the turbulent history of the Church of Scotland, there is a diagram and set of notes, based on those originally compiled by Linda Merle, which may be of assistance.
Scottish Catholic Archives at Columba House, Edinburgh holds some church records and has information about others. Most dioceses have deposited their historical records at Columba House, and retain only current records. Much material from Scots Catholic Colleges overseas is at Columba House. The Archdiocese of Glasgow and the Diocese of Paisley retain their historic records. At Columba House are Status Animarum from the early 19th Century (e.g. Glasgow 1808) - lists of all Catholics and in some counties (mainly in North East Scotland, e.g. Morayshire) lists of everyone. The National Records of Scotland has photocopies of all pre-1855 Roman Catholic parish registers.
Scottish Jewish Archive Centre is centralising Jewish records, building databases, and recording burials in Jewish cemeteries (or sections of cemeteries). Numbers of records are quite small.
Methodist records are in a number of archives. Generally records of rural churches went to university archives, records of city churches went to local authority archives.
Episcopal Church records also are in a variety of archives. It is best to search at the National Register of Archives to locate them. Some are at the National Records of Scotland.
After 1753, when English law forbad irregular marriages, a number of people who objected to marrying in a church wed in border centres where the couple's own consent to marriage before witnesses was legal under Scottish Law. Gretna is the most famous of these. Marriages were conducted by self appointed ministers at the border Toll booths along the few roads into Scotland.
Irregular Border and Scottish Runaway Marriages are addressed on the National Records of Scotland website.