Сергей Тетюхин родился 23 октября 1975 года в Ферганской области. Выступал за юношескую команду Узбекистана и ташкентское «Динамо», которые тренировал его отец Юрий Иванович. В 1992 году в связи с отсутствием серьёзных перспектив для роста игрока на родине, семья Тетюхиных приняла решение о переезде в Россию. Вместе с ещё одним воспитанником Юрия Тетюхина, Андреем Борозинцом, Сергей отправился в «Белогорье».
Как вспоминал главный тренер белгородского клуба Геннадий Шипулин, Сергей сразу произвёл приятное впечатление и хорошо смотрелся в разных амплуа:
В 1995 году Тетюхин выиграл с белгородским «Локомотивом» свой первый титул — Кубок России, в 1997 и 1998 годах становился чемпионом страны, а в 1999-м впервые был признан самым ценным игроком чемпионата, выиграв приз Андрея Кузнецова.
В сезоне-1999/2000 вместе с ещё двумя россиянами, Ильёй Савельевым и Станиславом Динейкиным, начал выступления в итальянской «Парме». Команда, проводившая первый сезон в серии A1 после возвращения из второго дивизиона, во многом благодаря российскому трио смогла занять пятое место в регулярном чемпионате.
В октябре 2000 года Тетюхин и игрок «Модены» Роман Яковлев по дороге в Парму попали в автоаварию. Сергей, находившийся за рулём, решился на обгон, но не справился с управлением и машина оказалась на встречной полосе. После лобового столкновения волейболисты чудом остались в живых. По счастью выжил и водитель встречного автомобиля, что упростило судебное разбирательство. Сергей перенёс несколько операций и пропустил почти весь сезон. Вернувшись в строй весной 2001 года, он вновь встретился на площадке с коллегой по несчастью Яковлевым — в четвертьфинальной серии чемпионата Италии «Парма» уступила «Модене» с результатом 1—3. Это были последние матчи Тетюхина в итальянской лиге.
Вернувшись в Белгород, Тетюхин в сезоне-2001/02 помог «Локомотиву-Белогорью» вернуть лидерство в российском волейболе — после 5-го места в предыдущем чемпионате команда, в которой он был капитаном, стала чемпионом страны и попутно дошла до финала Кубка CEV. В период с 2003 по 2006 год вместе с «Локомотивом-Белогорьем» выиграл ещё три чемпионата и два Кубка России, в 2003 году был признан самым ценным игроком «Финала четырёх» Лиги чемпионов, завершившегося первой в истории победой российского клуба, а также во второй раз в карьере стал обладателем приза Андрея Кузнецова.
В третий раз звание лучшего волейболиста России Сергею Тетюхину было присуждено в 2006 году. Тогда «Локомотив-Белогорье» проиграл суперфинал чемпионата страны столичному «Динамо», но лидер белгородской команды проявил незаурядные волевые качества. Накануне второго выездного матча суперфинала (первый был проигран железнодорожниками со счётом 0:3) Сергей на тренировке неудачно отбил летевший в лицо мяч и сломал палец. В том самом матче белгородцы проиграли первые две партии, но в третьем сете Тетюхин, выйдя на подачу, превратил счёт 3:6 в 7:6 и внёс перелом в ход игры. Всего же за пять партий он набрал 23 очка — почти четверть от всех, что заработала его команда, в том числе 10 непосредственно с подачи. «Локомотив-Белогорье» вырвал тяжелейшую победу и спас интригу в серии, в остальных матчах которой Тетюхин продолжал играть со сломанным пальцем.
Летом 2006 года вместе с партнёрами по белгородскому «Локо» Александром Косаревым и Вадимом Хамутцких перешёл в казанское «Динамо-Таттрансгаз». В суперфинале чемпионата России-2006/07 они взяли реванш у московских динамовцев за поражение годичной давности, а следующий сезон принёс Тетюхину победы в Кубке России и Лиге чемпионов и очередной приз лучшему игроку страны, после чего волейболист снова вернулся в «Локомотив-Белогорье».
С третьим за карьеру появлением Тетюхина в «Локомотиве-Белогорье» были связаны надежды болельщиков на новые успехи команды. Ведь с 1995 года, когда Сергей начал выходить в основном составе дружины Геннадия Шипулина, все российские клубы, за которые он выступал, в каждом сезоне выигрывали хотя бы один какой-либо титул. И традиция действительно получила продолжение — выдающаяся игра Тетюхина в финале Кубка CEV в Афинах против «Панатинаикоса» принесла почётный трофей волейболистам из Белгорода.
Осенью 2009 года Тетюхин уже в составе казанского «Зенита» выиграл свой 8-й национальный Кубок и был признан MVP «Финала восьми» в Калининграде, а в мае 2010 года в восьмой раз стал чемпионом России. В сезоне 2010/2011 во многом благодаря мастерству и многолетнему опыту Тетюхина «Зениту» удалось одолеть в финале московское «Динамо», набравшее ход к решающим стадиям плей-офф. 7 мая 2011 года Сергей Тетюхин стал 9-кратным чемпионом страны, тем самым ещё более упрочив своё лидерство по числу титулов в российской Суперлиге. После окончания сезона снова перешёл в «Локомотив-Белогорье».
Будучи универсальным волейболистом, Сергей Тетюхин одинаково сильно действует практически во всех элементах игры — в атаке, на приёме, в защите, в решающие моменты матчей может изменить игровую ситуацию в пользу своей команды сильной подачей или эффективным блоком, является по-настоящему «командным» игроком, бойцом на площадке, олицетворяющим уверенность, спокойствие, профессионализм и умеющим передать это состояние своим партнёрам по команде. Он пользуется огромным уважением у болельщиков независимо от их клубных пристрастий.
В 1994 году Сергей Тетюхин вошёл в состав молодёжной сборной России. На чемпионате Европы в Турции команда, возглавляемая Валерием Алфёровым, выиграла золотые медали. В финальной игре со счётом 3:0 были обыграны сверстники из Франции, а Сергея Тетюхина, выходившего на решающий матч с новокаиновой блокадой плеча, признали лучшим игроком турнира. За год до этого, в 1993-м, Сергей мог дебютировать и в национальной сборной. Он поехал вместе с командой в традиционное в те годы турне по Японии, но на площадку ни разу не вышел, поскольку был заявлен как третий резервный связующий.
Первый официальный матч за национальную сборную Тетюхин провёл 11 мая 1996 года в Пекине. В рамках Мировой лиги российские волейболисты в тот день одержали победу над сборной Японии со счётом 3:2. Сергей вошёл в заявку сборной на Олимпийские игры в Атланте. В декабре 1999 года стал обладателем Кубка мира и ему было присвоено звание заслуженного мастера спорта.
В 2002 году сборная России впервые выиграла Мировую лигу и взяла серебряные медали чемпионата мира. Сергей Тетюхин был одним из лучших игроков мирового форума проходившем в Аргентине. По итогам чемпионата он занял четвёртое место в споре самых результативных игроков, уступив только именитым диагональным Маркосу Милинковичу, Ивану Мильковичу и совсем немного — Владимиру Николову (135 очков против 139). Сергей также вошёл в десятку лучших принимающих, проявив себя в этом элементе эффективнее многих либеро.
Первую паузу в выступлениях за сборную Тетюхин взял в 2005 году, когда попробовал свои силы в пляжном волейболе. Через два месяца после начала занятий бич-волеем, Тетюхин и его коллега по «Локомотиву-Белогорью» Игорь Колодинский заняли 2-е место на третьем этапе чемпионата России в Белгороде, проиграв лишь сильнейшей на тот момент российской паре Роман Аркаев / Дмитрий Барсук. Но вскоре, на последнем этапе подготовки к чемпионату Европы-2005, Сергей вновь оказался в стане сборной России.
Наряду с Вадимом Хамутцких он является участником четырёх Олимпийских игр, серебряным призёром Олимпиады в Сиднее и бронзовым призёром Игр в Афинах и Пекине.
В октябре 2011 года впервые после чемпионата Европы-2009 был вызван в сборную России, вошёл в заявку на Кубок мира и во второй раз в карьере стал победителем этого турнира. Всего Сергей Тетюхин в период с 1996 по 2011 год провёл 279 официальных матчей за сборную России, что является рекордом. Его именем назван символический клуб, учреждённый газетой «Спорт-Экспресс» для игроков, сыгравших более 200 матчей за сборную.
Выпускник Белгородского педагогического института.
Женат, жена Наталья, сыновья Иван, Павел и Александр.