A starship was any manned spacecraft that was capable of viable interstellar travel, i.e. any manned spacecraft that has the ability to transport and support a crew across interstellar distances in a reasonable time. A starship accomplished this via the employment of some form of faster-than-light spacecraft propulsion technology, such as warp drive.
In the Federation during the 23rd century, starships were identified exclusively as vessels operated by Starfleet, or as stated by R.M. Merik, "a very special vessel and crew". (TOS: "Bread and Circuses") Within the Federation, starships were viewed as the role of protector within the civilian community, as starship captains were given a certain level of authority in the region they patrolled. (TOS: "Mudd's Women", "The Conscience of the King", "The Trouble with Tribbles") Generally limited to the roles of exploration and defense, starships typically did not transport cargo except in the case of an emergency. (TOS: "The Cloud Minders")
Design was also a factor in defining a starship. The configuration of a vessel, as identified by sensor scans, could be used in identifying a starship. (TOS: "The Doomsday Machine") Likewise, a starship could be identified on sensors by its power utilization curve, as a vessel utilizing 100% power had the ability to skew sensor readings. (TOS: "Journey to Babel")
Production materials reproduced in Stephen Whitfield's The Making of Star Trek suggested that the term "starship" was a unique designation for space-going vessels. In that vein, the USS Enterprise and her sister ships were originally designated "Starship-class" vessels. The dedication plaque on the bridge designates the ship as "USS Enterprise, Starship Class".
The term denoted a large, multi-purpose vessel capable of taking on a variety of tasks during an extended mission, often at some distance from central authority. (The nearest 24th century equivalent designation would be that of Explorer.) This helps explain Merrik's reference to a "very special type of vessel and crew" ("...Kirk commands, not just a spaceship, but a Starship".), as well as the numerous references to the extraordinary amount of authority granted the captain of such a ship.
However, in Star Trek: The Motion Picture, as well as everything afterwards, the term fell into a more "generic" use, first as describing Federation vessels in general, and then large, faster-than-light-capable vessels from a range of cultures.
Likewise, the "NCC" registry was originally to be used only for the self-same Starship-class vessels, just like the modern CVN registry is used for nuclear-powered aircraft carriers of the United States (example; USS Enterprise CVN-65). That, too, as of TMP, has become "generic" among Starfleet ships. The NCC was inspired by the modern NC registry for non-commissioned (civilian) ships in the military. Since the Starship was an exploration vessel first and combat vessel secondary, Gene Roddenberry liked the parallel.