Фамилия Терюхова хранит память о прозвище или имени дальнего предка, и у неё есть две основные версии происхождения. Согласно первой, в основе лежит прозвище Терюх, связанное с глаголом «терять». В «Толковом словаре живого великорусского языка» В. Даля есть родственное слово «теряха» — так называли растеряху, беспорядочного и беззаботного человека, у которого всё пропадает. Выходит, прозвище Терюх указывало на рассеянность или беспечность предка, и потомки такого человека со временем стали Терюховыми.

Вторая версия ведёт фамилию к производной форме имени Терентий — Терюх. Само имя восходит к греческой основе со значением «молотящий хлеб» или «растирающий краску». В этом случае основатель рода был человеком из простого сословия, и фамилия закрепилась за его детьми как отчество по уменьшительному имени.

Родственные именования встречаются в исторических документах. У С. Веселовского упоминаются Теряй Дмитрий Иванович Сорокоумов-Глебов, конец XV века, и его сын Михаил Дмитриевич Шат Теряев, 1531 год. Эти примеры показывают, что прозвища и фамилии от основы «теря-» бытовали в русской среде уже несколько столетий назад.

Какая версия правдоподобнее? Обе имеют право на существование, но прозвищная — от «терять» — выглядит более естественной для народной среды, где фамилии часто возникали из насмешливых или бытовых характеристик человека. Имя Терентий было распространено, но форма Терюх от него менее типична, чем, скажем, Терёха. Впрочем, без точных родословных записей утверждать что-то однозначно нельзя.

Фамилия Терюхова образована по стандартной русской модели: к основе Терюх добавили суффикс -ов, указывающий на принадлежность потомку, а окончание -а — женская форма. Мужской вариант — Терюхов. Такая фамилия не относится к дворянским или книжным, она выросла из живого народного прозвища, а значит, предки носителей были скорее всего крестьянами или посадскими людьми.