I was going to mention distillation as an effective means of desalinization, but you beat me to it.
Salt is one of the hardest things to get out of water. I am not sure, but would reverse-osmosis be effective? I am not too familial with all the methods of water purification, but I know that since salt completely dissociates in water it is impossible to filter it out using mechanical filtration methods. Dissolved salt is no longer salt, it is sodium ions and chloride ions.