The mechanical generation of threads is essentially a very simple process and the following article outlines the basic principles - but does not attempt to cover the details, as already published many times.
A book with screwcutting information most suitable for the amateur (and ideal to refresh the memory of the professional) is "The Amateurs Lathe". This gives a complete breakdown of the process with simple-to-follow instructions that will enable even the complete beginner to cut threads successfully. Other useful publications with complete  instructions threads and screwcutting include the inexpensive: "Screwcutting in the Lathe" and a newer, beautifully produced hard-back book: "Screwcutting"
Gear-train calculators to help with screwcutting, typical arrangements of changewheels, generating pitches not on a chart, discovering what gears make a complete set, generating metric to imperial and imperial to metric transposing gears, etc. can be can be found here
How was the first thread generated? You can repeat the process yourself. Take a wooden rolling pin and place it on a flat surface. Pick up a knife, hold it horizontally and place the sharp edge on the top surface of the roller near one end and twist the blade a little horizontally, say 10º or so, press down and use it to roll the pin away from you. As the pin rolls a spiral line is generated. Deepen the cut line into a V-shaped groove and you have a thread. Unfortunately, unless you are the cook of house, you now in dead trouble with SWMBO and need to get on Amazon double quick and order another. Threads are size according to their outside diameter and the number of turns per inch. e.g. 0.75" x 10 t.p.i. (0.75" in diameter and ten threads per inch). Or, for metric threads, on their outside diameter and the distance between the crests of the thread e.g. M10 x 1.5 would be a 10 mm diameter thread with a distance between the crests of 1.5 mm. The pitch of a thread is best measured with a "thread gauge" of the type available from any machinery dealer, though with care and good eyesight a steel ruler can be used.
Threads are not an invention of the mechanical age: Hero of Alexander had devised a method of generating larger ones two thousand or more years ago - and for centuries cabinet and clock makers had been making their own by hand, as did railway repair shops when they made batches of the crude, hand twisted, coarse-pitch screws used to hold rail-keeper plates to wooden sleepers.. However, starting with the Industrial Revolution, and continuing through 1800s, a need arose as never before for nuts, bolts and threaded fittings in a bewildering variety of types and sizes. The situation today, following decades of research into sometimes times-conflicting requirements and world-wide adoption of the metric system (except in the USA) is a huge number of thread types and hundreds of different designs of "fastener". However, despite this apparent complexity, the essential elements of threading on a lathe are simple. For thousands of years the lathe remained, in essence, a potter's wheel turned on its side and capable, in engineering terms, of only the simplest work. Its first use for screwcutting was nothing short of a revolutionary step for, by using a train of gears to connect the lathe spindle to a long screw running along the length of the bed - and the screw to the lathe carriage - the latter, together with its cutting tool, could be forced to move a set distance for every revolution of the spindle. If the workpiece revolved eight times and the cutting tool was arranged, by the gearing, to move exactly one inch, then a spiral would be cut with 8 turns per inch - otherwise known as 8 t.p.i. (t.p.i. = threads per inch).

Although the long threaded rod along the bed was originally termed a master thread, or leading screw, it is now generally referred to as the leadscrew. Any leadscrew needs to be very accurately made (they are often produced by specialist manufacturers, not the machine-tool builders themselves) with an Acme, square or other thread form optimised for the task - but never with a standard Whitworth or Metric form - as unfortunately found on many cheaper lathes from the Far East. The leadscrew will reproduce its exact pitch (hence the need for accuracy) on the material to be threaded - providing it can be driven directly in some way from the headstock spindle - usually by ordinary straight-cut gears but occasionally by bevel gears, epicyclic drives or even, in a few cases, using toothed belts. Of course, with the advent of computer control, the relative movements of spindle and carriage are easily manipulated electronically - hence, it's now possible to generate threads with no need for any mechanical connection between spindle and carriage).
A side benefit of screwcutting was the realisation that an automatic and hence steady feed along the bed produced a much improved surface finish, especially if the feed was slow and the tool correctly shaped. Thus, for everyday-use the changewheels are normally arranged to provide a very fine feed to the carriage; to set them for screwcutting means removing most or all of them and building up a fresh train following the instructions on a "screwcutting chart" (normally attached to the machine). At the end of the threading job the screwcutting train is removed and the fine-feed gears replaced. This time-wasting work can be largely avoided if a screwcutting gearbox is fitted - hence their popularity in industry. However, not even a full "quick-change" screwcutting gearbox can generate every pitch of thread and it is sometimes necessary to substitute changewheels in order to extend the range of the box - or generate metric threads from an English gearbox, or visa versa. Despite the attractions of a screwcutting gearbox for amateur use (quick and simple gear selection), as the saving of time is not usually as consideration (except for the indolent) a lathe fitted with changewheels provides a much more adaptable machine.
If the lathe's changewheel chart is missing, all is not lost, the book, Screwcutting in the Lathe will help to calculate a fresh set. Further help can be found in a set of instructions for using changewheel calculators, and the necessary program downloads, can be found here.
As already explained, driving the cutting tools by a direct mechanical connection with the headstock also allowed, in ordinary work, a much smoother and more consistent finish - and at the same time greatly reduced the fatigue suffered by the operator. This form of powered motion was originally called self-acting or self-act - and both terms were once widely used to distinguish between plain-turning and screwcutting lathes.
When the carriage is connected to the leadscrew some form of "nut" is used: this can be either solid and permanently engaged or either a single or double "clasp nut" that the operator can engaged and disengage at will. However, once the "clasp nuts" have been opened, and the carriage moved back to allow another cut to be taken, the problem arises of how to re-engage the nuts at the correct point--a problem solved by a simple but ingenious device, the "Dial Thread Indicator". The DTI consists of a gear engaged with the leadscrew but mounted on a shaft with a dial plate at the other end engraved with lines so that the operator, by following charts (that vary with the pitch of thread being cut), can safely engage the nuts and continue threading accurately. Unfortunately, an interesting difficulty arises when cutting metric pitch threads on an English lathe - or vice versa - the leadscrew nuts must not be disengaged and the lathe has to be "electrically reversed" back to a start point each time a new cut is taken.
Different Threads:
The first question that springs to the mind of the novice is: "Will my lathe be able to cut different types of thread?"  (Whitworth,  British Standard Fine, American National Coarse, British Standard Brass, American National Fine, British Standard Brass, Unified National Coarse, Unified National Fine, British Association, British Cycle Standard, Metric, etc.) The answer is, yes. Providing the lathe has the changewheels necessary to gear the spindle to the headstock so that the tool moves the right distance whilst the spindle revolves once - it can be done. The 'form' or "shape" of the thread (which, simply put, is what makes the essential difference between the "types" of thread, not their pitch) is entirely in the 'shape' of the tool (or tools) used to cut it. The tool can be ground to replicate any thread angle at will; if you wished, for example, you could even invent your own; first however check this link or this one: they list and explain many of the threads forms both current and obsolete. Of course, not all is quite so simple, and at the end of this introductory article is a simple explanation of one of the confusing differences between metric and Inch threads.
A History Lesson:
Sit up at the back--a test follows: the two engineers most closely associated with the development of mechanically-developed screw threads (although they did not invent the process) were both active in the 1800s: Henry Maudsley (1771 - 1831) "Machine Builder" of London, England (the "engineer's engineer") and one of his apprentices, Joseph Whitworth (1803 - 1887) Toolmaker of Manchester, England known for his plain-speaking not to say blunt ways (and probably the epitome of Shaw's dictum that "all progress depends on the unreasonable man."). Maudslay was the first engineer able to make, and exploit, a very accurate screw thread. His masterpiece was a screw 5-feet long and 2-inches in diameter (1525 mm by 51 mm) with fifty-turns per inch (50 per 25 mm) on which ran a nut twelve-inches (305 mm) long with 600 threads. The apparatus was designed to average out pitch errors over small distances and was a vital element in the process of engraving the scale markings on astronomical and other very accurate measuring devices. Maudslay went on to manufacture a range of screwcutting lathes (using the principle of a "master thread" or "leading screw") examples of which can be seen in the London Science Museum and the Henry Ford Museum in Dearborn, Michigan, USA. Astoundingly, so accurate were Maudslay's threads (and so precise his measuring equipment). that he was able to observe the expansion effect of sunlight warming one half of a leadscrew. Whitworth was a prolific inventor, toolmaker and designer (and millionaire businessman) who brought a disciplined approach to engineering. His design and development skills ranged across almost the whole field of mechanics but, following the publication in 1841 of his: "On a Universal System of Screw Threads" he is best remembered for his success in standardising what was, at the time, a chaotic system of hand-fitted, non-interchangeable fastenings. Having collected a large sample of nuts and bolts from a variety of workshops and examined their properties, he proposed a system whereby the ratio between the depth of the thread and its pitch was maintained over a range of sizes - and that the angle of the thread be 55 degrees. The system was employed in his own workshops by 1858 and was quickly taken up by other engineers as its benefits of simplicity and interchangeability - to say nothing of its recommendation by the greatest living British engineer of the day - became obvious.

Forming Threads by Hand:
It is possible to generate threads on a revolving cylindrical surface without using mechanical assistance by employing a "chaser". These look rather like wood-turning chisels with a "thread form" cut into their end or side faces and are made from hard steel - tool steel for the finest-quality ones - and vary in width and thickness according to their thread pitch and job they have to do.
The full-sized type are normally fitted to stout wooden handles to give the necessary purchase (which can be considerable) and are expensive. However, there is a cheaper alternative, the chasers that come from automatically-releasing die holders; these units are used on capstan lathes and hold four small identical sections of tool steel formed with a very accurate thread along one edge. If these are removed and mounted in a suitable metal  holder they can be used exactly like their full-size cousins. Unfortunately,  using either type is difficult and beginners are well advised to avoid them completely - although they can have a role to play in "cleaning up" a mechanically-cut thread and imparting a radius or other shape to the crest and root of the thread, a process not possible with the single-point thread generation method described above. In use the chaser is rested against a suitable support - with some lubricant between the two - and fed into the workpiece on centre height with a steady sliding motion.
Continued below:

Whitworth thread form with 55 degree angle and rounded roots and crests. Other threads have flat crests with rounded roots, or visa- versa, or both crest and root can be flat. The angle can also differ - standard metric threads are 60 degrees - whilst some threads are "square cut" at 90 degrees. Whilst the "single point" tool commonly used in a lathe can cut the angles correctly, it cannot generate the radii at root and crest - and these are sometimes formed in the post-machining stage  by the use of a hard steel "chaser".

Basic form of the single-point threading tool used to cut external threads.

An essential part of the screwcutting toolkit - a threading gauge marked with the common thread angles. This allows the tool to be set "square" to the work, as illustrated below.

Using a thread gauge to set the tool for internal threading. The gauge is held against a plate pressed against the accurately turned end of the tube which is to be threaded.

The cutting edge of an external chaser.

Continued:
With skill (and luck for the beginner) the chaser will bite into the surface and begin to form a spiral cut; as the other points on the chaser engage with the spiral, the action becomes, to an extent, self-stabilising and easier to perform; however, many passes are normally required before the full depth of thread is generated.
Chase Screwcutting
Another form of thread chasing is mechanical in nature and sometimes employed on precision and special production lathes, can be seen here. The system was probably invented by Joseph Nason and awarded a patent 10,383 in America on January 3, 1854.
Metric Threads
An interesting difference exists between "English" threads (a definition that includes American types) and Metric. All English (sometimes called "Imperial") and American threads are based on what happens within the boundary of a single inch length. Inside that inch length you might have any number of turns (pitches) - though typically restricted on lathes with either changewheels or screwcutting gearboxes to a range extending from 2 to 56 t.p.i . The usual pitch limit for threads on nuts and bolts is 40 t.p.i., an ME (model engineering) specification, above that they are cut only for special purposes). Metric threads are arranged differently, there is no fixed length into which the pitches must fit and each is arranged to be a fraction, or multiple of, a millimetre. The effect of this is illustrated if you take the centre of a valley anywhere on a threaded rod (with a pitch in whole inches) and measure one inch in either direction - the finish point will also be in the centre of a valley. However, if the pitch is a fraction, say 6.5 t.p.i., then you have to measure two inches, to accommodate the effect of the fractional 1/2). Metric pitches are designed so that the valleys centres are a fixed distance apart in whole millimetres or fractions of a mm - for example: 0.25 mm, 0.75 mm, 1.0 mm, 1.5 mm, 2.5 mm, etc. If you measure a metric thread as for an inch type - but using a fixed unit of metric length (such as 100 mm) - you will find that while some pitches do end in a valley centre, most do not - because they don't divide exactly into 100. While for all practical purposes this difference does not matter, it creates an interesting effect when screwcutting using a lathe for, although just a single gear is needed on the thread-dial indicator of an English-threading lathe, on a metric machine two and sometimes three are required to span the range of common pitches. In fact, an impractical six gears (or two or more indicators equipped with necessary gears) would be required to cover every metric-pitch requirement.
What might be the world's most commonly "used" thread - as in "used" for doing up and undoing things rather than being a permanent fastening (such as the multi-trillion-production bicycle spoke)? Let's stir up a hornet's nest and suggest the long-lived 1/4" x 20 t.p.i. Whitworth thread found in the base of almost every camera to allow the attachment of a tripod (it's common to all makers and every model they produce - though some heavier professional types have been, as a concession to hard use, fitted with either two sockets or a single more robust 3/8" x 16 t.p.i.). Are the tops of toothpaste tubes all a common size, or limited to just a few? If so, that fitting may be a contender as well.
Fine Feeds
If you don't want to screwcut but just need a super-fine feed to the carriage to give a fine finish to turned jobs, the gears are arranged in a "compound" thus:
a) End of leadscrew: fit the largest gear available from the changewheel set (often a 70 or 75t)
b) Driving the leadscrew gear is a pair of gears (Set B) pinned together on one shaft: the larger of the pair will be the second largest in the changewheel set, the smaller gear the second to smallest.
c) On the shaft above Set B is another pair of gears pinned together (Set C) consisting of the third largest gear in the set together with the smallest gear in the set,
d) Driving Set C will be a small gear, usually on the output shaft of the tumble reverse assembly.
Of course, being able to do this depends upon having all the gears in the set - usually from 10 to 14 for a typical small lathe. In some case the very largest gear may be too large to work with the compounded gears (or may not fit under the gear cover) and may be intended for an inch-to-metric or metric-to-inch conversion (in which case they may be marked as having 127 or 135 teeth..

A typical arrangement of changewheels driving down to a screwcutting gearbox - in the case a Boxford Model VSL lathe.
The picture also shows the clever but simple lever-operated "tumble-reverse" mechanism by which means the direction of drive to the leadscrew (and power-shaft if fitted) can be reversed and the carriage caused to move either towards or away from the headstock.
In its neutral, central position it allows the headstock spindle to revolve without driving any of the gears. Moving the engagement lever up or down (the spindle must be stationary of course) engages one or other of a pair of tumble gears below the spindle gear causing the next gear in the train to revolve either clockwise or anticlockwise. The lever is usually, but not always, spring loaded in some way, with a plunger that engages in one of three holes in either the front or side face of the headstock. On all types of tumble-reverse mechanism, the stud gear is usually made removable, allowing it to be part of the screwcutting train and providing a quick and easy means of slowing down or speeding up the minimum carriage feed rate..