In the 22nd century Federation Starfleet vessels generally seemed to have 3-digit registry numbers, just like the Daedalus-class vessels USS Archon NCC-189 and USS Horizon NCC-173 (Star Trek Encyclopedia). We do not know that for sure though, for visual records of such hull numbers are missing. In the 23rd century registries with 4 digits were common, including the famous USS Enterprise NCC-1701, most likely several other Constitution-class ships and the USS Excelsior NX- (later NCC-) 2000. Finally, another digit has been added in the 24th century, as it can be seen on the hulls of Sisko's USS Saratoga NCC-31911, the USS Voyager NCC-74656 and numerous more Starfleet ships. This is why we can surmise that the registry number of a starship at least roughly correlates with the time when it was commissioned.
In case of chronological registries the increasing number of digits hints at an exponential increase in the number of starships. This would indicate that Starfleet consists of more than 10,000 starships in the mid- and late 24th century if we presuppose an average lifetime of a couple of decades for a single vessel. At the first glance this abundance does not seem to to be in accordance with most of TNG and early DS9 episodes when starships appeared to be scarce and the 39 ships destroyed in the Battle of Wolf 359 (TNG: "The Drumhead") appeared like a heavy loss. On the other hand, as Shelby mentioned in TNG: "The Best of Both Worlds II", it would take about one year to rebuild the fleet, so Starfleet must have sizable ship building capabilities, probably enough to sustain a fleet of thousands of vessels. A number in the thousands is also realistic taking into account how many ships fell victim to the Dominion War. It started with the 98 ships of the Seventh Fleet in DS9: "A Time to Stand", and subsequently several hundred more must have been destroyed in the big battles in DS9: "Sacrifice of Angels", "Tears of the Prophets", "The Changing Face of Evil", "What You Leave Behind" and countless skirmishes that were not even mentioned.
Ship registries by classes
The above chart shows all known registries sorted by ship classes. If registries are chronological, this may provide an impression of the production times of the single classes too. Some classes like the Excelsior, Miranda and especially the Oberth have a very broad range of registries, indicating a very long construction period. The chart below plots the given registries over time. The yellow dots denote mentions of ships which are in active service for an unspecified time, whereas the green dots represent ships which have just been commissioned. Assuming that the new ships always have the highest existing number, one may connect all the green dots and the highest orange dots to a line which indicates the registry limit and perhaps the number of ships ever commissioned. One thing to note is the aforementioned roughly exponential increase over time until about 2360. The other remarkable fact is that the latest registries of the 2360s and 2370s don't rise that rapidly any longer, despite the many new ship classes, advances in technology and the recent Borg confrontations and Dominion War.
Ship registries over time
Registries as design codes
There are a number of theories that Starfleet's registries could have a significance beyond being a simple chronological number for each individual vessel. It was an early attempt to explain the Enterprise's registry NCC-1701 in that it could stand for the 17th design or class of ships, and that it was the second ship of that class (after the Constitution NCC-1700). Likewise, if not a class, the "17" could denote heavy cruisers or another more general type of vessels in a similar fashion as an "F" plus a number denotes frigates in the NATO registry system. Alas, there are very few occurrences of registries among ships of the same class that are accordingly close together (e.g. USS Monitor NCC-61826 and USS Merrimack NCC-61827, USS Defiant NX-74205 and USS Valiant NCC-74210). Other than that, the closest known registries of most classes span many hundred numbers (like the NCC-26xxx in the Ambassador class or the NCC-60xxx and NCC-61xxx in the Nebula class). Even if for some reason large number ranges were skipped, the known registries would still not be close enough to maintain the realistic idea that there are at most one or two hundred ships of these classes of capital ships. Ultimately the idea that the ship class is encoded in the registry fails considering how the registries of the Galaxy class and the Nebula class intersect in the NCC-71xxx range and the registries of Defiant and Intrepid in the NCC-72xxx region. Almost all recently (2368-2375) commissioned ships have registries in the range from NCC-72000 to NCC-75000, regardless of their class. In other words, the gaps in the registry system are apparently not empty but routinely occupied by ships of other classes and of completely different types.
Shared numbers with civilian vessels
A simple rationale for the high registries in the 24th century could be that not only Starfleet ships but also other Federation vessels are included in the registry system, which is corroborated by the S.S. Vico NAR-18834 and some other civilian science ships or freighters, where NAR seems to denote research vessels not belonging to Starfleet. Yet, an orbital shuttle had the registry NAR-25820 as soon as in 2293 ("Star Trek VI: The Undiscovered Country"). Perhaps the civilian registry scheme is totally independent of the Starfleet NCC numbers, meaning that every prefix is using the full range of numbers.
Introduction of runabout registries
It is also possible that every runabout has its individual registry in the 24th century, whereas this type of vessel did either not exist or was numbered as belonging to a home starbase or a starship in former times. Assuming there are several thousand of them, this could be another explanation for the high 24th century registries.
An alternative explanation is that Starfleet simply started skipping hundreds of registry numbers beginning about at NCC-2000. This may explain why there is no known number between NCC-21000 and NCC-26000 or between NCC-46000 and NCC-50000, for instance. The reason for leaving out ranges of hundreds or perhaps thousands of numbers may have been that the true number of Starships should not become obvious to potential enemies at the first glance.
Registries with checksum
It is also possible that, rather than an obvious code for the design or class, the numbers include some kind of checksum which could, for some reason, be the middle digit of the five-digit numbers.
Some single registries are not within reasonable limits. For example, the number of the Oberth-class USS Grissom ("Star Trek III: The Search for Spock") is NCC-638. If all starships are successively numbered, this means that the Grissom is much older than the original Enterprise, though she looks rather contemporary to the Excelsior. In the 24th century, moreover, Oberth-class starships are not only still in use, but even new ones seem to have been commissioned, as e.g. the USS Cochrane NCC-59318 (Star Trek Encyclopedia). It is hardly believable that starships are constructed based on the same design for more than 150 years, while on the other hand there is a great variety (about 50 to 60 confirmed yet) of different classes with apparently short life spans of only two or three decades. A famous oddity is the lettering of Matt Decker's USS Constellation as "NCC-1017" (TOS: "The Doomsday Machine"). This was obviously done by rearranging the number "NCC-1701" of the AMT Enterprise model kit. The trouble is that the registry number of the class ship USS Constitution is NCC-1700 (so the Enterprise would be the second ship of this class). An explanation for almost all registry numbers that do not match the scheme is that starships were not necessarily chronologically numbered until the end of the 23rd century. It is possible that numbers of decommissioned ships were routinely reissued, perhaps even denoting new ships with the same name. According to such a regulation it would have been no problem to number the second starship Enterprise as NCC-1701 after the first one had been destroyed in "Star Trek III: The Search for Spock". This points at a change in the registry scheme at about the time when the Excelsior was commissioned.
Registries for vessels under construction
It is possible that a registry is assigned to a vessel as soon as it is ordered by Starfleet or as construction begins at the fleet yards. This could be the reason why the USS Bradbury NX-72307 has a higher number than the USS Sutherland NCC-72015 that was featured in a later episode as a newly commissioned ship. It could even explain the NX-59650 of the USS Prometheus being completely out of range for a brand new ship. With the exception of this vessel, however, the given registries for new ships do increase monotonically, although the time for their development and construction may vary considerably.
Summarizing, as a matter of fact the known registries of Starfleet vessels may only roughly correspond with the ages of the ships. None of the various theories accounts for all of the inconsistencies, so it should be tolerated that ships are sometimes arbitrarily numbered. Real-world numbering systems like on passports or car number plates are not based on a perfectly obvious system either. In my view it is a stretch if fans speculate too much about registry oddities that they would easily accept in the real world.
Other Starfleet Ship Classes - uncertain and unknown
Uncertain Ship Names and Registries - a collection of typos and other oddities