Sometimes there is no difference- i.e. if one is referring to a below-ground-level space to store stuff then it can be called either a "basement" or a "cellar" (although a "cellar" tends to imply a smaller space than a "basement"). However, when the space is designed to be a habitable area, it can only be called a basement (often specifically called a "finished basement"). For example, most houses and apartment buildings in the Midwest of the United States have below-ground levels. If the space is habitable and someone's room/living space is on that level, he/she would say "I live in/I rent/My room is in/My apartment is in the basement." (It would sound strange to say "I live in the cellar" (this gives the mental image of living in a small storage space with a rough concrete floor, unpainted walls, etc.)
It's partly a question of dialect too. The house (in southwestern Ontario) I grew up in had a "cellar" not a "basement," and to go there we would "go down cellar." On the other hand, as you say, cellars are often storage spaces, such as a "wine cellar." Our house had "coal cellar" where the coal was kept (until we got central heating) and one corner of the barn was "root cellar" (where root crops such as turnips and mangels were stored).