Navvy first appeared in print in these quotations:
1832-1834, De Quincy, Wks. "If navvies had been wanted in those days."
1839, Lecourt, Birmingham Railways 27, "The banditti, known in some parts of England by the name of 'navies' or 'navigators' and in others as 'bankers'... "
1862, Smiles, Engineers, III, 321, "During the railway-making period the navvy wandered about from one public work to another."

The OED standard definition is "A labourer employed in the excavation and construction of earth-works, such as canals, railways, embankments, drains, etc." Although chiefly British, in the States it has come to mean an unskilled laborer (seldom heard). Webster's Collegiate. Both references declare that the word is derived from 'navigator.'

In Britain, it also came to mean the machine that did excavation work.