No, it is not true that necessarily the deeper you get the cooler it gets.
For really deep holes it is actually the opposite, the deeper you get the warmer the temperature gets. This is called the Geothermal Gradient. This states that temperature goes up 25C per 1KM of depth
.
For the first couple of meters the temperature will likely drop or raise (depending on the above ground temp) dramatically. But it will then level off and begin to slightly increase. This is because your moving away from the influence of the Sun and start to be influenced by the temperature of the earth's core.
For a root cellar, you're not going to go 1km deep (obviously). You really need to think of a root cellar as a way to maintain (roughly) a constant temperature. The depth (that your likely to dig) alters this slightly but not much. This temperature could be hotter or colder than the temperature above ground, as shown in the picture below which are taken from http://www.builditsolar.com/Projects/Cooling/EarthTemperatures.htm.

This figure shows the maximum temperature deviation from the annual average is dampened out at about 30 feet depth. You can refer to the figure´s source for more detailed information, i.e. on seasonal changes.