The nickname for North Carolina is The Old North State or The Tar Heel State (North Carolina's state song also has the title and theme of Old North State). See state nicknames for all 50 states.

History:

King Charles I granted territory in America in 1629 to Sir Robert Heath (his Attorney General) to be named Carolina, or the province of Carolina (the same charter also refers to the province as Carolana or New Carolana).

The Carolina province consisted of all the land lying between "the Ocean upon the east side & soe to the west & soe fare as the Continent extends itselfe...." The northern border was to be the 36th parellel (roughly a line from Kill Devil Hills to Knoxville, Tennessee). The southern border was the 31st parallel, which extended the province through current-day Georgia (the state border between Florida and Alabama follows the 31st line of latitude).

King Charles II granted a new charter to the Lords Proprietors for the same territory in 1663 and two years later the charter expanded the colony north to 36° 30' (extending the territory to approximately the current North Carolina-Virginia border, and south to 29° N latitude (just south of Daytona Beach, Florida).

The Old North State

In 1710 the Carolina colony was divided, when Edward Hyde was appointed by the Lords Proprietors to be "...Governour for North Carolina Independent of the Governour of South Carolina." The southern part was called South Carolina and the older, northern settlement North Carolina. This was when the nickname "Old North State" was born.

The Tar Heel State

Less clear is the origin of the nickname Tar Heel State. Most historians agree that the nickname stems from North Carolina's long history as a producer of naval stores (tar, pitch, rosin and turpentine from the state's extensive pine forests). North Carolina was a world leader in naval stores production from about 1720 to 1870. The following is from North Carolina State Library (North Carolina Nicknames):

Various stories and legends have sprung up to explain where the name came from. Perhaps the most popular is found in Histories of the Several Regiments and Battalions from North Carolina in the Great War 1861-1865 (edited by Walter Clark):

Thus after one of the fiercest battles, in which their supporting column was driven from the field and they successfully fought it out alone, in the exchange of compliments of the occasion the North Carolinians were greeted with the question from the passing derelict regiment: "Any more tar down in the Old North State, boys?" Quick as thought came the answer: "No, not a bit; old Jeff's bought it all up." "Is that so; what is he going to do with it?" was asked. "he is going to put it on you'ns heels to make you stick better in the next fight." ...

Source:

North Carolina Nicknames: NC State Library
North Carolina Quick Facts: Ben's Guide to US Government

Links:

State Nicknames - 50 States
North Carolina History: NC State Library