All the BMD and census (1841-1911) records for Scotland are available at http://www.scotlandspeople.gov.uk
which is the government website. Keep in mind that government registration in Scotland did not begin until 1855 (unlike England where it began in 1837). Parish records are also on scotlandspeople. It is a pay to view/download site, but very reasonable.