Let’s say a person born in the 19th century had the name “Mikhail Shatunov”, does the surname “Shatunov” mean a nick name or does it mean that an actual person named “Shatun” was his father/grandfather?
This depended on the person's social class and where in Russia they were from. Before the abolition of serfdom, serfs, as a rule, didn't have or use surnames. If a serf was named Михаил Шатунов, it most probably meant that he was the son of a man with the nickname Шатун.
Nobility, of course, did have surnames.
By the XIX century, merchants, clergy, people in state service, converted Jews — pretty much every Orthodox Christian subject of the Empire who was not a serf, had had a hereditary surname for at least a hundred years.
If it were just a nickname, was that nickname chosen by the person’s parents at birth or was it given as a nickname by their village.
Serfs mostly got their nicknames from census reports (ревизские сказки). It was up to the estate managers what they wanted to name them. They were named after their father's given name or nickname, for the most part, but sometimes the estate managers got creative. The plot of Nicholai Gogol's "Dead Souls" revolves around a scam involving those census reports. It, among other things, mocks the creativity of the census takers.
Members of the clergy got surnames upon graduating from a seminary. Sometimes their original surnames were not deemed worthy of a man of the cloth, so they were forced to change it. Those surnames are usually derived from saints' names, Latin and Greek terms, church terminology and so forth. Again, the church hierarchs sometimes got really creative about naming people.
Other people usually got their surnames when applying for a passport, so they usually got to choose their own.
I don't know how 19th century Russians used to register births (perhaps there was no birth registry at the time).
The parishes maintained vital records, for which there was no general standard format. They usually recorded the parents' names, surnames or nicknames (if they had them), the date and the place of birth, and the baby's Christian name.
When did the tradition of assuming surnames begin in Russia?
At different times for different social classes and different regions: from the XI century to the late '1930s.
