Фамилия Потудины — редкий случай, когда прозвище, лёгшее в основу, сохранило почти дословный разговорный оборот. В её центре — глагол «потудить», который в старых русских говорах означал «потрубить», «погудеть» или «поиграть на гудке». Гудок — старинный смычковый инструмент, предшественник гуслей и гудка-скрипки. Соответственно, Потудой в народе могли прозвать музыканта-импровизатора, который «потуживал» на свадьбах и ярмарках. Суффикс -ин указывает на принадлежность: Потудин — буквально «сын Потуды» или «из семьи Потуды».

Словообразовательная модель здесь нестандартная. Обычно фамилии от глаголов образуются через причастия или названия профессий (Кузнецов, Плотников). Потудин же — отглагольное прозвище в форме повелительного наклонения или краткого обозначения действия: «он тот, кто потудит». Это роднит фамилию с такими редкими примерами, как Гуляев или Балалаев, но с более узким, музыкальным значением.

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

По географии фамилия тяготеет к северным и центральным областям России, где гудок бытовал дольше всего — в Архангельской, Вологодской, Костромской губерниях. Встречаемость крайне низкая: по некоторым данным, Потудины — единичные роды, не образующие крупных гнёзд. Сословно предки могли быть как свободными крестьянами-музыкантами, так и дворовыми людьми, развлекавшими бар. В письменных источниках фамилия фиксируется не ранее XVIII века, что типично для прозвищ, перешедших в наследственные фамилии в среде непривилегированных сословий.