I saw this explained by Utah Phillips somewhere along the line. The laborers on the railroads were called Gandy dancers because they used shovels made by the Gandy company. To lift the rails so that the rock could be tamped under them, the laborer would get out on the end of the shovel and use the shovel as a lever to lift the rail, hence, Gandy dancing. At least that's the way I remember it.