Traditionally the operation of a mechanical tool was determined by the physical constraint of the position/type/size of the gears used. So if you wanted to change a tool setting, you would have to manually make an alteration to the gear(s). Many machines worked this way, even ones you would not think of, such as printing presses, folding machines, etc.
Therefore, using a gear for settings is a metaphor that has made its way into our visual language lexicon. If you want to change how 'something' operates you need to alter the inner-workings of the system, which was often the gears.
Another metaphor for its use is that of a traditional watch. In fact many watches are now designed so that the user can see the actual inner workings.
In terms of software, Windows 95 introduced a 'gear' as part of its Settings Start Menu option. This is the first use of it I'm aware of in terms of software. Refer to image below:
In more recent times, the original iPhone OS (introduced in January 2007 but not available to consumers until June 2007) used a detailed gear icon for its Settings. This has been maintained (and enhanced) within recent versions of Apple's iOS. Apple then also adopted a similar icon for it's System Preferences in Mac OS X 10.5 which was released on 26 October 2007.
The popularity of iOS helped to encourage broader adoption of the gear icon as a metaphor for settings, and a plethora of gear icons have appeared on digital imaging stock libraries (e.g. iStockphoto.com) in recent years.
As for what was used to portray 'settings' before a gears icon, you would have to assume that there was no need for such an icon until the onset of graphical user interfaces. And, since Apple were the first to use a graphical user interface in the mainstream with the launch of the Macintosh computer in January 1984, you'd probably have to go back to when the Mac OS first introduced a Control Panel. As far as I'm aware, the first control panel was introduced in February 1986 with Mac OS 1 (which was actually the fifth version of the OS). Initially the control panel was just a single desk accessory type application containing all the settings within it, and this had no icon associated with it at all. See the Mac OS 1 screenshot below for how this appeared:
Despite many improvements over the years, this approach remained largely the same. The screenshot below is from Mac OS 6 introduced in April 1988 (that's right, from Mac OS 1 to Mac OS 6 in only two years). Note the lack of icons next to the Control Panel option):
It wasn't until the launch of System 7 in May 1991 that control panels and preferences were separated into individual small application-like processes accessible from two folders within the System Folder. Custom folder icons were introduced to portray these and neither contained gears, cogs, wrenches or screwdrivers! Instead they used a 'slider' and 'dials' (or radio buttons). In the Mac OS 7.0.1 screenshot below note the folder icons for Control Panels and Preferences:
Mac OS 8 (launched in July 1997) updated these icons, but they were newer reflections of the existing ones. Note in the screenshot below that they're still folder icons using sliders and dials/buttons (not cogs/gears etc). This is important because Mac OS 8 was launched after Windows 95 which did use a cog/gear to portray settings (hence my earlier notion that it was probably the first software to do so).
Going back now to your question of how many teeth it takes to make a cog/gear look like a settings symbol, please refer to this free online course covering the topic of designing gearbox icons as a way to portray options, settings, etc.