Very often, "cellier" is a room where things liked bottled fruit etc. are stored, so to me, a kind of "larder"; it may well not be underground, but often conveys the idea of a food store.

"cave" is usually more what we think of as a cellar; note, though, that even so, it may not be underground! In your case, it may well be a cellar specifically for storing wine, though soemtimes it is used in a much more egenral sense as a glory-hole (cf. the cages or other storage facilities in the basements of blocks of flats)

I don't think you can make any assumptions about size or even location, it's more to do with their function.

--------------------------------------------------
Note added at 2 days3 hrs (2007-02-25 12:16:02 GMT)
--------------------------------------------------

If this is indeed a 16th c. "wine-grower's" house, then I think you can fairly safely assume that this usage is going to be typical of old houses, with the "cellier" as some kind of food store and the "cave" as probably principally a wine cellar. Sometimes they will be located in different places, like cellier on the ground floor next to the kitchen, or in some outbuilding, whereas the cave could well be (semi-)underground; but sometimes, you find them adjacent in the basement (or elsewhere!) — it's really odd when some throws open a door and says "voici le cellier", and then the door next to it and says "et voilà la cave !"

It might be considered that a "cave" will have been specifically intended to stay cool all year round, and to this end, very often had an earth floor, whereas the cellier might possibly have been kept a little drier. However, as with all these things, there are about as many different possibilities as there are old houses!