i changed from large gravel to sand...err, am still changing. rather than pull apart the whole tank and do it in one huge project, i've been changing over a period of months. right now the tank is about 80% sand, 20% large gravel, which i've left in for longer than i'd intended because one of my spiny eels seems to oddly prefer that portion. what i did was basically remove the gravel a little at a time while i was doing water changes and began to add sand to those sections. did they mix in parts? sure, but that didn't bother me much. and i also lost some sand i'd put in to replace the gravel as i removed gravel, but at $2 a bag for sand, i wasn't too broken up about it.
going the opposite way, i would think, should be easier, because you can just suck sand or small gravel out with a large enough hose. just add the gravel in cups, a little at a time, so there's not an avalanche falling on your fish.
my sand-based substrates took a lot longer to clear up to crystal-clear water than gravel tanks, but i prefer the look, and i think my fish do as well. also, my plants have always grown better in the sand.