Родился 23 сентября 1975 г. в гор. Маргилане Ферганской обл. Узбекской ССР (ныне Узбекистан) в семье Юрия Ивановича и Любови Аблякимовны Тетюхиных. Родители - заслуженные тренеры России по волейболу.
В 1996 г. окончил факультет физической культуры Белгородского государственного педагогического университета.
Начал заниматься волейболом в Фергане, первым тренером был отец. Учась в последнем классе школы, стал выступать за клуб "Крылья Востока" (Ташкент).
В 1992 г. семья переехала в Россию. По совету заслуженного тренера СССР по волейболу Юрия Фураева, Тетюхин перешел в команду "Белогорье" (Белгород, в 1993-1995 гг. - "Локомотив", в 1997-2001 гг. - "Белогорье-Динамо", в 2001-2011 гг. - "Локомотив-Белогорье"). Выступая на позиции доигровщика, в составе этого клуба провел сезоны 1992-1999 гг., 2001-2006 гг., 2008-2009 гг., 2011-н. в.
Вместе с "Белогорьем" семь раз выиграл чемпионат России (1997, 1998, 2002-2005, 2013), восемь раз - Кубок страны (1995-1998, 2003, 2005, 2012, 2013), дважды - Суперкубок России (2013, 2014), три раза - Лигу чемпионов, ежегодное соревнование ведущих клубов континента, проводящееся Европейской конфедерацией волейбола (ЕКВ; 2003, 2004, 2014), один раз - чемпионат мира среди клубов (2014).
В 1999-2001 гг. играл за итальянский клуб "Парма" из одноименного города.
С 2006 по 2011 г. выступал за казанскую команду "Динамо-Таттрансгаз" (с 2008 г. - "Зенит"), в составе которой трижды стал чемпионом страны (2007, 2010, 2011), а также победителем Лиги чемпионов (2008), обладателем Кубка (2007, 2009) и Суперкубка России (2010).
Являясь волейболистом молодежной сборной России, в 1994 г. стал чемпионом Европы, а в 1995 г. - победителем мирового первенства.
Первую встречу за взрослую сборную России провел 11 мая 1996 г. в Пекине (Китай). В тот день в рамках Мировой лиги - наиболее престижного ежегодного коммерческого турнира национальных команд - россияне одержали победу над японцами.
В составе сборной Тетюхин в 2012 г. стал чемпионом летних Олимпийских игр в Лондоне (Великобритания), в 2000 г. - серебряным призером Олимпиады в Сиднее (Австралия), в 2004 и 2008 гг. - бронзовым медалистом Олимпиад в Афинах (Греция) и в Пекине. В 1999 и 2011 гг. выигрывал Кубок мира - представительный турнир национальных команд, проводящийся один раз в четыре года. В 2002 г. стал победителем Мировой лиги.
3 августа 2016 г. был официально объявлен знаменосцем сборной России на летних Олимпийских играх в Рио-де-Жанейро.
В общей сложности провел за сборную 312 матчей и набрал 2 тыс. 418 очков. Является рекордсменом среди российских волейболистов по этим показателям.
В сентябре 2013 г. был избран от партии "Единая Россия" в городской совет Белгорода.
В сентябре 2015 г. стал депутатом Белгородской областной думы VI созыва от "Единой России", является заместителем председателя комитета по регламенту и депутатской этике.
В декабре 2017 г. присоединился к общественному движению Putin Team ("Команда Путина"), созданному российским хоккеистом Александром Овечкиным.
В декабре 2023 г. был зарегистрирован в качестве доверенного лица кандидата на пост главы государства Владимира Путина (президентские выборы пройдут в РФ в марте 2024 г.).
Заслуженный мастер спорта (1999).
Награжден орденами Дружбы (2001) и Почета (2012), а также медалями ордена "За заслуги перед Отечеством" I и II степени (2009, 2005). Почетный гражданин Белгородской области (2012).
В 1999, 2003, 2006 и 2008 гг. получал приз Андрея Кузнецова - награду, присуждаемую изданием "Спорт-Экспресс" лучшему волейболисту российского чемпионата. В 2016 г. был признан официальным онлайн-каналом ЕКВ самым ценным игроком европейского отборочного турнира на Олимпийские игры в Рио-де-Жанейро. В 2012 г. был признан лучшим спортсменом России по версиям Федерации спортивных журналистов России, "Спорт-Экспресса", интернет-портала "Чемпионат".
В октябре 2021 г. Сергей Тетюхин был введен в Зал славы волейбола (Холиок, шт. Массачусетс, США).
Женат. Супруга - Наталья, предприниматель. Дети - Иван (род. 1998, волейболист команды "Технолог-Белогорье"), Павел (род. 2000, волейболист команды "Белогорье-2") и Александр (род. 2010).