Given Federation size (4.1 x 10e10 to 6.15 x 10e10 cubic light years) and assuming 9000 c as standard speed for warp drive, we can take some guesses.
In TNG "Redemption" we hear that there are "only 12 ships within day's travel of this position". That gives sphere with radius of 24.64 light years, for volume of sphere being 62 667.9 cubic light years. With that, we have 1 starship per 5 222 cubic light years, for total of 7.85 million ships. That is little too much, given size of fleets during Dominion war; it does imply large number of starships around single starbase.
However, in most incidents there is at least one ship within two days of travel, which gives us sphere with radius of 50 light years per ship, for total volume of 523 598 cubic light years per ship. That gives fleet of 78 304 to 117 456 ships. If we assume that "within range" means 3 days of travel, then we have 74 light year radius per ship, for 1 697 398 cubic light years per ship. That gives fleet of 24 155 to 36 232 starships.
In BobW we know that 39 ships will take less than a year to replace. Given lifespan of ~80 years, we have fleet from 3120 to 6240 ships, assuming timeframe from 6 months to full year. Absolute upper limit, assuming one month to replace ships, would be 18 000 capital ships, which might fit with 30 000 k fleet suggested people working on DS9, if we account for likely expansion of fleet in meantime, as weel as older ships being likely pressed into war service.
There are 119 known starbases. However, if starbases are numbered sequentially, then we have 718 standard starbases, 9 Deep Space stations, 7 Deep Space "K" stations, 9 Xendi starbases, 6 "G" starbases and 10 named starbases, for total of 759 starbases. Also, numbering scheme of "standard" starbases rises between TOS and TNG, implying it is sequential, with each starbase getting number - so Starbase 710 is older than 711, but newer than 709.
In TOS "Court Martial" we have 10 starships listed as being under repairs, giving us ship-to-starbase ratio of 10:1, for total of 7590 starships.
On other hand, we have this screensot:
There we can see 2 Galaxy class starships, 6 excelsior class starships, and 8 Miranda class starships, all of them being apparent mainstays of fleet in their 'weight category' (heavy - medium - light). That gives us 12 144 starships at least, considering only 3 classes are shown. However, it is likely that one starbase supports far more ships on average.
Another way is by using NCC numbers; these seem to be sequential like Starbase numbers, but are not reliable for counting capital ships due to one very simple reason - even runabouts have them. Still, NCC numbers during TNG are in 60 000 and during DS9 in 70 000 range, giving (when accaunted for possible losses) ~30 000 to 50 000 ships, including runabouts.
Federation fleet that was going to retake DS9 consisted of "elements" of two full fleets, with each element being 300 ships. Thus we can assume 600 to 900 ships per fleet, with 900 ships per fleet being most likely due to tendency of modern fleets to have only 1/3rd of entire fleet on sea at any given time, rest being refueled, repaired etc. Highest fleet number we heard about is 10, and, since fleets were newly-formed, there is no reason to assume gaps in numbering system. Therefore, we have between 6 000 and 12 000 starships; I will take middle value of 9 000 ships as conclusion, since Starfleet ships are mostly designed to be extremely self-sustainable.
However, since it is elements of two fleets, number might be doubled or tripled, giving 1200 to 2700 ships per fleet, for total of 12 000 to 27 000 ships in Starfleet.
On the other hand, people working at DS9 suggested 30 000 ships. Also, prevalence of Excelsior and Miranda class ships suggests big bulding spur in late 23rd and early 24th century, thus making 27 000 - ship fleet more likely, and allowing us to explain BobW statement with Federation at time producing low numbers of higher-quality ships (Galaxy class as compared to Excelsior and MIranda classes) and reduction of shipbuilding rate due to long time of peace.
It seems logical that each of Federation's 150 member worlds has its own shipyards, since one of prerequisites for joining Federation is to have your own warp drive. On Memory Alpha we have this list of shipyards:
40 Eridani A Starfleet Construction Yards - capable of building starships up to size of Nebula class, at least. Located in 40 Eridani A systems in Sol sector
Antares Ship Yards - capable of building ships up to Defiant size, at least. Located in Bajor sector
Baikonur Cosmodrome - builds ships both for civilian use and for Starfleet
Beta Antares Ship Yards - can build ships up to Prometheus size, at least. Possibly part of Antares ship yards.
Copernicus Ship Yards - can build ships up to Conctellation class size, at least. Located in orbit of Luna (Earth's moon).
McKinley Station - presumably capable of building ships of Nebula/Galaxy size. Located in Earth orbit.
Marin County Starfleet yards - from alternate future, possibly exist in normal timeline as well. Capable of building ships up to Olyimpic class
Oakland Fleet Yards - alternate future
San Francisco Fleet Yards - capable of building ships of Sovereign class at least
Tranquility Base - located on Moon. Capable of building ships up to Constellation class, at least
Utopia Planitia fleet yards - key Federation R&D and shipbuilding facility. Can build all ship classes, at least 16 starships simultaneously (based on number of drydocs seen here).
Assuming 10 starships can be built simultaneously at each shipyard on average, and assuming 1 year needed to construct average starship (USS Defiant, class prototype, needed 5 years, and it was prototype. USS Valiant was launched 2 years after Defiant), we get 110 ships per year. With 80-year lifespan (althought some evidence indicates ship can last 100 years - we see some ships with registries around NCC-1000 during TNG), we get 8 800 ships; however, not all ships survive for even that long, which gives us 6 000 to 7 000 capital ships as optimal number.
CONCLUSION: Starfleet has 6 to 27 thousand ships.
