Tarheel first appeared in print in 1869 in the Overland Monthly:
"A brigade of North Carolinians... failed to hold a certain hill, and were laughed at by the Mississippians for having forgotten to tar their heels that morning. Hence originated the name tar heels." From the OED, 1987 and later eds.
The name appeard in a diary entry for 1864, the writer speaking of "a poor, starving tarheel at Elmira." Park, pub. in Southern Hist. Soc. papers, 1876.

However, tar_heel is correct, the term alluding to an important product of North Carolina in the 19th century. All major referencs accept this. The name is older than the quoted references.
Walt Whitman printed a list of state nicknames, supposedly from the Broadway Journal for May 1, 1845. (H. L. Mencken, "The American Language") This has not been verified.
Another quote from 1889, Jour. American Folk-lore: "The mountain 'tarheel' gradually drifted into a condition of dreary indifference to all things... but hogs and hominy." (OED)
The appelation is now respectable. A recognized nickname for the state is the Tarheel State, and a North Carolina University football team is known as the 'tarheels." (Sorry, can't remember if it is UNC or NCSU at the moment- getting forgetful).

The "tarhood" has been used since the 18th century as a general collective term for sailors, but this apparently has no bearing on the American usage.