I used to drink a lot of soda every day. I quit cold turkey when I started eating Paleo. You just have to have the willpower to do it.
During the day, I'll have water that I add lemon and lime juice to, with a tiny pinch of salt. No sweeteners. The lemon/lime mix is very refreshing, and they have a lot of electrolytes. Sometimes I'll have the same thing with dinner.