I recall that it has something to do with workers (loggers?) putting tar inside their shoes (in the heel) to keep them from slipping off while working.
Of course, I’m a U of MD grad (GO TERPS!!!) and hope that the truth of the “tarheel” is just as silly as my story.
IIRC, it actually had to do with shipbuilding. In the days of wooden ships, NC provided a lot of the wood and pine tar (used to seal the ships hull) during construction.
As I post this, the talk show guest on WPTF 680 AM in Raleigh, NC is the author of “Y’all Spoken Here”. This topic came up, and he endorsed the Pine Tar explanation. He also noted there is a controversy whether it is one word or two.
During the War of the Revolution (between the colonists (who eventually become the U.S.) and the British), some British military person (unknown?) commented that the fighters from North Carolina “stuck” to the British (hounded, pursued, badgered) “like tar on the heel of a boot”.
The North Carolinians took this as a complement, and proudly referred to themselves as “tarheels”.