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

В отличие от фамилий на -ов/-ев, которые образуются от основ на согласную (Иван — Иванов), суффикс -ин крепится к основам на -а/-я (Гнилушка — Гнилушкин). Это одна из самых распространённых моделей в русской ономастике, но здесь интересно другое: прозвище Гнилушка не было редким в северных и центральных губерниях России. В переписных книгах XVI–XVII веков встречаются крестьяне и посадские люди с таким прозвищем — например, в новгородских и вологодских землях. Оно могло закрепиться за человеком, который жил в сыром месте или торговал гнилым лесом, но скорее всего, это была насмешливая характеристика.

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

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