Palusinski is how its always been to me
Probably Palusiński. Not a common surname, but it exists, with about 700 people in the country bearing that name. Highest concentration in Lublin, but scattered all over the country. From a village/hamlet/estate called Palusin or Palusino, no information on which exists. See:
Second choice is an unrelated name Paluszyński. Even rarer, with about 370 people bearing that name, with the highest concentration near Konin. From a village/hamlet/estate called Paluszyn or Paluszyno, no information on which exists. See:
The names of both places is derived from the word "paluch", a form of "palec", which means "finger" or "toe". Remember, these are two different surnames that are unrelated. They are not different spellings of the same name.
Based on the distribution and low numbers, it's a pretty safe bet that you are related to either all the Palusiński's, or, less likely, to all of the Paluszyński's. That depends on how dependable the person who told you how your name should be spelled is.
The name Paluczyński also exists, but is very rare indeed, with about twenty people living mostly in Rawicz. See: