The original "NCC-" designation seems to have begun in the high 1600s according to Memory Alpha, with the U.S.S. Constitution (NCC-1700) beginning the Constitution-class line, and the original Enterprise being next out of drydock.
While the ship bearing the name Enterprise has always kept the designation NCC-1701 (with one or more letters to designate "generations"), the rest of the Starfleet ships were numbered according to some regular system, such that the U.S.S. Voyager (roughly contemporary to the Enterprise-E) has the designation NCC-74656.
From this numbering, absent some system buried in the numbers, one would assume that Starfleet has commissioned nearly 73,000 starships with the NCC- numbering system, which does not seem to be used for smaller support craft like shuttles or freighters, between the original Enterprise in the early 2250s to Voyager in 2371 (only about 120 years). That is a LOT of ships to maintain in that time period, or alternately to build and then lose.
Breaking it down, to build 73,000 ships in 120 years would require sustaining a build pace of approximately 608 ships per year, and if we take into account that a starship takes up to 3 years from commencement to christening, then up to another year in and out of drydock for shakedown and outfitting, we're talking about at least 1800 ships being in the shipyards under construction at any given time.
There may be other explanations of course; the numbering system may have been advanced due to some event or rearrangement (The USAF and Navy had different airplane numbering designations for planned and produced designs, until the Joint Chiefs agreed to a shared numbering scheme involving a "reset"), and ships are commissioned and recommissioned, possibly taking on a new number for their new mission (at least two ships that became Enterprises were under construction while another Enterprise served, and thus likely had a different designation planned).
However, my original theory, that the number was some system of ship class number and ship number, seems to be incorrect. It follows for certain ship classes such as Constitutions (they're all "17"), but the Miranda-class, probably the most long-lived design in Star Trek canon, has designations beginning with 18xx (Reliant was 1864) up into the 31000s (Sisko's Saratoga was NCC-31911) with notable ship designations in the 1900s and 21000s. The Excelsior-class, probably the most successful in terms of ships produced, started with NCC-2000 and has designations in the 2500s, 14000s, 38000s, 42000s and even one up in the 62000s, contemporary to Voyager.
So, the question stands; approximately how many Federation starships were commissioned through the known Star Trek canon? Is there any rhyme or reason to ship designations in-universe?