Hard water contains calcium and magnesium ions. Water softeners remove those ions by exchanging them for sodium or potassium ions. Two factors contribute to that slippery-when-wet feeling you get after soaping up with soft water. First, soap lathers better in soft water than in hard water, so it's easy to use too much. The more dissolved soap there is, the more water you need to rinse it away. Second, the ions in softened water lessen its ability to 'stick' to the soap molecules, making it more difficult to rinse the cleanser off your body.
The reaction between a triglyceride molecule (fat) and sodium hydroxide (lye) to make soap yields a molecule of glycerol with three ionically-bonded molecules of sodium stearate (the 'soap' part of soap). This sodium salt will give up the sodium ion to water, while the stearate ion will precipitate out of solution if it comes into contact with an ion that binds it more strongly than sodium (e.g., the magnesium or calcium in hard water). The magnesium stearate or calcium stearate is a waxy solid that you know as soap scum. It can form a ring on your tub, but it rinses off your body. The sodium or potassium in soft water makes it much more unfavorable for the sodium stearate to give up its sodium ion so that it can form an insoluble compound and get rinsed away. Instead, the stearate clings to the slightly charged surface of your skin. Essentially, soap would rather stick to you than get rinsed away in soft water.
There are a few ways you can address the problem. You can use less soap, try a synthetic liquid body wash (synthetic detergent or syndet), or rinse with naturally-soft water or rainwater (probably won't contain elevated levels of sodium or potassium).