A contraction of navigator. One employed to make railways.
“Canals were thought of as lines of inland navigation, and a tavern built by the side of a canal was called a `Navigation Inn.' Hence it happened that the men employed in excavating canals were called `navigators,' shortened into navvies.” —Spencer: Principles of Sociology, vol. i. appendix C, p. 834.
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Navvy from Infoplease: