"One legend has the nickname being applied to the state's residents as long ago as the Revolutionary War. According to this story, the troops of British General Cornwallis were fording what is now known as the Tar River between Rocky Mount and Battleboro when they discovered that tar had been dumped into the stream to impede their crossing. When they finally got across the river they found their feet completely black with tar. Their observation that anyone who waded North Carolina rivers would acquire tar heels led to the nickname first being used."

               --From the same place as Amos's explanation, goheels.com