In 2016 multiple subjects changed their timezones, including: Novosibirsk, Sakhalin, Tomsk, and Zabaykal'ye.

Russia stopped observing daylight saving time, and shifted all its time zones one hour later, starting 2011-03-28. The overall effect was that clocks were turned ahead on that date as if it were for daylight saving time, but actually to set them to the new standard time. They will not be set back an hour in the fall.

Russia has changed the time zones of some federal subjects. The two farthest east, Chukot and Kamchatka, have moved their standard time from UTC+12 to UTC+11. Samara and Udmurt are moving from UTC+4 to UTC+3. Kemerovo will change from UTC+7 to UTC+6, as previously announced. All these changes take effect on 2010-03-28. That means that those subjects' clocks will stay unchanged while clocks in the rest of Russia are moving forward an hour.

At some date around 2006, according to the tz database, Astrakhan', Kirov, Saratov, and Volgograd switched from UTC+4 to UTC+3.

Tomsk's standard time has switched from UTC+7 to UTC+6. Altay and Gorno-Altay switched to UTC+6, temporarily, as it turns out. No information as to when they changed.

Russia has changed the time zones of some more federal subjects. Altay, Astrakhan', Gorno-Altay, Magadan, Sakhalin, Ul'yanovsk, and Zabaykal'ye are all setting their clocks ahead one hour. These changes took effect on or about 2016-03-27.

Rules currently in force

Notes:
For many years, rail and air schedules throughout Russia have used Moscow time. Clocks in railroad stations and airports are set to Moscow Time, even where it differs from local time by as much as eight hours.
Sources disagree about the exact extent of some time zones. Also, a few divisions have more than one time zone.

Time zone history

The tables below were up-to-date in about 2001. I haven't had time to revise them for later changes.

Source: This information was adapted from the tz database. Zone names come from that database. The names don't necessarily match any names used in the "real world".

Example: When it was 14:18 (or 2:18 p.m.) local time on 2000-09-03 (September 3, 2000) in Sochi, Russia, what was the UTC?

Sochi is in the state of Krasnodar. From the first table, Krasnodar is in the Europe/Moscow time zone. (This is a specialized meaning of "time zone", which is more precise than common usage.) In the second table, look in the block of rows for Europe/Moscow. Among them, look for the first row on which the Final Date exceeds 2000-09-03 14:18. You find that the eighth line has a date of "Present", which is the first to exceed 2000. Looking across the row, the Russia rule applies, and standard time is UTC+3. Finally, look in the third table under the Russia rule. Once again, find the date range that includes the date in question (2000-09). That would be the last range, "1996 onward". This rule says that daylight saving time was in effect from 02:00 [a.m.] of March 26, 2000 to 03:00 of October 29, 2000 for Sochi. The date in question does in fact fall between those two dates, so daylight saving time was in effect. Therefore, the local time was standard time plus one hour, or UTC+4. Subtract four hours from the given time to get UTC. The answer is 2000-09-03 10:18 UTC.

Time zone names

The tz database contains names and abbreviations for the Russian time zones. They were created by a contributor. The only ones that are known to have been commonly used in Russia are MSK and MSD.

MSK and MSD represent Europe/Moscow since 1919. There is no recognized long form for these abbreviations, but they evidently mean Moskva and Moskva/DST. According to a contributor to the tz database, they were created for use by Unix-like operating systems on Moscow computers. Applying them to dates before about 1980 is an intentional anachronism.
Central European (Summer) Time, abbreviated CE(S)T, represents Europe/Kaliningrad during 1945.
Eastern European (Summer) Time, abbreviated EE(S)T, represents Europe/Moscow in 1922-1930 and in 1991, and Europe/Kaliningrad since 1991.
Moscow Mean Time, abbreviated MMT, represents Europe/Moscow during standard time from 1880 to 1917.
Moscow Summer Time, abbreviated MST, represents Europe/Moscow when observing standard time plus one hour during 1917 and 1918.
Moscow Double Summer Time, abbreviated MDST, represents Europe/Moscow when observing standard time plus two hours during 1918 and 1919.
Kuybyshev (Summer) Time, abbreviated KUY(S)T, represents Europe/Samara from 1919 to 1991. (The name of the city was changed from Samara to Kuybyshev during approximately that period.)
Samara (Summer) Time, abbreviated SAM(S)T, represents Europe/Samara since 1991.
Sverdlovsk (Summer) Time, abbreviated SVE(S)T, represents Asia/Yekaterinburg from 1919 to 1992. (The name of the city was changed from Yekaterinburg to Sverdlovsk during approximately that period.)
Yekaterinburg (Summer) Time, abbreviated YEK(S)T, represents Asia/Yekaterinburg since 1992.
Omsk (Summer) Time, abbreviated OMS(S)T, represents Asia/Omsk since 1919.
Novosibirsk (Summer) Time, abbreviated NOV(S)T, represents Asia/Novosibirsk since 1919.
Krasnoyarsk (Summer) Time, abbreviated KRA(S)T, represents Asia/Krasnoyarsk since 1920.
Irkutsk Mean Time, abbreviated IMT, represents Asia/Irkutsk during standard time from 1880 to 1920.
Irkutsk (Summer) Time, abbreviated IRK(S)T, represents Asia/Irkutsk since 1920.
Yakutsk (Summer) Time, abbreviated YAK(S)T, represents Asia/Yakutsk since 1919.
Vladivostok (Summer) Time, abbreviated VLA(S)T, represents Asia/Vladivostok since 1922.
Magadan (Summer) Time, abbreviated MAG(S)T, represents Asia/Magadan since 1924.
Kamchatka (Summer) Time, abbreviated PET(S)T (for Petropavlovsk-Kamchatskiy), represents Asia/Kamchatka since 1922.
Anadyr (Summer) Time, abbreviated ANA(S)T, represents Asia/Anadyr since 1924.

References:
Standard Time Zones of the World  map from the CIA World Factbook
Russia Time Zone Map 
USSR: Time Zones : map of time zones as of March 1982
Timezones in Russia  (in Russian)
Map of Russian Time Zones  (in Russian)