The suffix -ski is a continuation of Proto-Slavic -ьskь-jь. It defined belonging and was also used for creation of adjectives:
As for surnames, at first it was used to create surnames of Polish nobility in the 13th century - surnames were made up of a city/town/village name which belonged to a particular noble family and the suffix -ski was added at the end:
City: Tarnów = surname: Tarnowski
City: Zamość = surname: Zamojski
Later surnames with the suffix -ski became more common. For example, one of the most common surnames in Poland is Kowalski. It probably denotes someone's profession since "kowal" means "a smith" (blacksmith) in Polish. It's an equivalent of the English surname "Smith".
And does it really sound different in Polish names than in Russian?
I guess it does since from what I can see in Russian a long "y" ("й") is added at the end:
In Polish there's only the short "i" ("и") at the end, without the long "j" ("й").