Actually, it has not been proven that skis melt the snow. This may be true for ice skates, but for a surface area as large as the bases of a pair of skis, it would take too much energy to melt even a microscopic layer of snow without noticing it slowing you down. When fresh snow warms up, you get snow sticking together by the effect discussed by freestyler540 above, combined with a suction effect onto the bottom of your skis. When the snow gets to corn conditions, this doesn't happen anymore because there is enough water between frozen pieces, so the pieces don't stick together, and the pieces are large enough, to not form a uniformly flat surface to suction onto your skis.