Russia doesn't prevent it's citizens from traveling. What prevents it's citizens from traveling is getting a VISA to the destination country. This is granted through the local Embassy or Consolidate of destination country requiring a VISA.

Permanent residency is not citizenship. Granting Permanent Residency will give him some sort of stability knowing he will not have to renew his status every year (or so) and be able to participate more fully in Russian society (ex: Employment, services, travel, Pension, etc).

Edward Snowden will always be a US Citizen in the eyes of the USA unless he takes steps to renounce his citizenship.