Точное происхождение данного слова на данный момент не установлено. Мне больше других кажется вероятной следующая теория.
Считается, что до XVIII века мужской половой орган было принято называть словом "уд" (поговаривают даже божок такой был). Однако где-то в этот же период, подобные словечки стали табуированными (не без помощи церкви, кстати). Вот только предмет вопроса никуда не делся и называть его в речи как-то надо было. В те времена венерические болезни были распространены больше, чем сейчас грипп, и вот в дворянской среде стал использоваться эвфемизм (этически допустимая замена) — латинское местоимение hoc (“это”). Скорее всего его ввели в употребление привычные к латыни лекари. Угодливо сообразуясь с нравами своих богатых пациентов, они назначали лекарство “для этого” (родительный падеж) или “этому” (дательный падеж), что по-латыни звучит соответственно как huius и huic. Менее образованные пациенты русифицировали ученую латынь. Возможно, например, что форму дательного падежа huic они воспринимали как деминутив, и, питая уважение к собственному детородному органу, предпочитали называть его “полным” именем "х*й".
В подтверждение этой гипотезы замечу, что примеры такого словообразования хорошо известны. Например, заимствованное в XVIII в. из голландского языка слово zondek, означающее “прикрытие (dek) от солнца (zon)”, зазвучало по-русски как зонтик и вскоре стало восприниматься как деминутив от слова зонт.
Так родилось новое русское слово, не имеющее аналогов в других языках (это лингвистическое явление называется редеривацией).
Однако я не лингвист, эту версию читал в интернете, за верность не ручаюсь, но звучит убедительно. Впрочем, некоторые лингвисты утверждают будто корень "х*й" древнеславянский, однако я не нашёл упоминаний его использования в известных берестяных грамотах (хотя и они, понятно довольно скудный источник). Зато, например, в
новгородской берестяной грамоте № 955 упоминается слово "пи*да", так что можно быть уверенным, это слово использовали уже в XII веке и уж оно-то точно древнеславянское.