The etymology of fuck has given rise to a great deal of speculation, which should be regarded skeptically. The authoritative Oxford English Dictionary is quite cautious in providing an etymology for this word. In the quotation below, the dictionary's usual abbreviations are spelled out for clarity:

Early modern English fuck, fuk, answering to a Middle English type *fuken (weak verb) [which is] not found; ulterior etymology unknown. Synonymous German ficken can be shown to be related.
The first known occurrence, in code because of its unacceptability, is in a poem composed in a mixture of Latin and English sometime before 1500. The poem, which satirizes the Carmelite friars of Cambridge, England, takes its title, "Flen flyys," from the first words of its opening line, "Flen, flyys, and freris"; that is, "Fleas, flies, and friars". The line that contains fuck reads "Non sunt in coeli, quia gxddbov xxkxzt pg ifmk." The Latin words "Non sunt in coeli, quia," mean "They [the friars] are not in heaven, since when though." The code "gxddbov xxkxzt pg ifmk" is easily broken by simply substituting the preceding letter in the alphabet, keeping in mind differences in the alphabet and in spelling between then and now: i was then used for both i and j; v was used for both u and v; and two v's were used for w. This yields "fvccant (a fake Latin form) vvivys of heli." The whole thus reads in translation: "They are not in heaven since they fuck wives of Ely (a town near Cambridge)." From The American Heritage Dictionary, 4th Edition.

As the OED notes, some have attempted to draw a connection to the German word ficken (to fuck, in dialects: to rub, to scratch, and historically to strike).

Other possible connections are to Latin futuere (hence the French foutre, the Italian fottere, the Romanian fute, the vulgar peninsular Spanish follar and joder, and the Portuguese foder). However, there is considerable doubt and no clear lineage for these derivations. These roots, even if cognate, are not the original Indo-European word for to fuck; that root is likely *h3yebh-, ("h3" is the H3 laryngeal) which is attested in Sanskrit (yabhati) and the Slavic languages (Russian yebat`, Polish jebać), among others: compare Greek "oiphô" (verb), and Greek "zephyros" (noun, ref. a Greek belief that the west wind caused pregnancy). However, Wayland Young (who agrees that these words are related) argues that they derive from the Indo-European *bhu- or *bhug-, believed to be the root of "to be", "to grow", and "to build". [Young, 1964]

Spanish follar has a different root; according to Spanish etymologists, the Spanish verb "follar" (attested in the 19th century) derives from "fuelle" (bellows) from Latin "folle(m)" < Indo-European "bhel-"; ancient Spanish verb folgar (attested in the 15th century) derived from Latin "follicare", ultimately from follem/follis too.

A possible etymology is suggested by the fact that the Common Germanic fuk-, by an application of Grimm's law, would have as its most likely Indo-European ancestor *pug-, which appears in Latin and Greek words meaning "fight" and "fist". In early Common Germanic the word was likely used at first as a slang or euphemistic replacement for an older word for "intercourse", and then became the usual word for "intercourse". Then, fuck has cognates in other Germanic languages, such as Middle Dutch fokken (to thrust, copulate, or to breed), dialectical Norwegian fukka (to copulate), and dialectical Swedish focka (to strike, copulate) and fock (penis). A very similar set of Latin words that have not yet been related to these are those for hearth or fire, "focus/focum" (with a short o), fiery, "focilis", Latin and Italian for hearthly/hearthling, "foc[c]ia/focac[c]ia", and fire, "focca", and the Italian for bonfire, "focere". But these words came from New Latin, centuries after Middle Dutch.

There is perhaps even an original Celtic derivation; futuere being related to battuere (to strike, to copulate); which may be related to Irish bot and Manx bwoid (penis). The argument is that battuere and futuere (like the Irish and Manx words) comes from the Celtic *bactuere (to pierce), from the root buc- (a point). An even earlier root may be the Egyptian petcha (to copulate), which has a highly suggestive hieroglyph. Or perhaps Latin "futuere" came from the root "fu", Common Indo-European "bhu", meaning "be, become" and originally referred to procreation.