La planta que menciona Ferran Buireu en su respuesta viene recogida en el Fichero General de la RAE también como gayumba, lo que le daría incluso aún más veracidad a la teoría, dado que de ahí a gayumbo apenas hay un paso. Y más aún, hay textos que directamente mencionan la planta como gayumbos:
[...] los gayumbos, que en marzo se cubren de sus perfumadas y doradas flores, con la profusión con que otras plantas se cubren de hojas [...].
Fernán Caballero (Cecilia Böhl de Faber), "Clemencia", 1852 (España).
Por cierto, en el Fichero General aparece recogido gayumbos como "calzoncillos" en el Diccionario de argot español y lenguaje popular de 1980, de Víctor León. Aunque en la hemeroteca de la BNE he podido encontrar un uso de la palabra muy anterior:
Las escenas que presenciamos con motivo del traslado de los heridos tenían, aparte lo trágico, una nota en extremo pintoresca: gitanas jóvenes y viejas se encontraban a la puerta de las clínicas llorando amargamente, y a la salida
de las víctimas pretendían abrazarse a ellas, gritando desaforadamente:
—¡Ay, probesito de mi arma! ¡Destrosaíto va der to! ¡Dime er perro negro que te jirió!
Otra exclamaba:
—¡Mírale con los gayumbos y los alares ensangrentaos! ¡Justicia grande pa el ladrón, que malos mengues se coman vivo! ¡Paloma, corderito mío, tú no jiciste mal arguno!
La Voz (Madrid). 5/5/1927, página 3.
Por tanto, se ve que a principios del siglo XX ya existía la palabra, y además su origen apunta al habla gitana. De hecho, según los artículos enlazados por la otra respuesta, se documenta su uso en 1905 en el Diccionario del argot español, de Luis Besses y Terrete. En una novela de 1912 se usa también, curiosamente necesitando una nota a pie para aclarar su significado:
—Es lo mismo, don Rodri. Yo no hablo como usted. Hablo como aquel que dice en gayumbos (4), como deben de hablar los hombres. Lo demás es perder el tiempo.
José Francés, "El sabor de la sangre", 1912 (España).
La nota (4) dice simplemente "calzoncillos". (Texto aquí, consultar página 119.)
Existe otra conexión posible, y es que gayumbo era como se denominaba al "toro que corría enmaromado", o al "toro de cuerda que se corre de noche poniendo en las calles grandes hogueras". Se trata de un toro con una cuerda atada en la cabeza y usado en algunos festejos. Pero ignoro qué conexión pueda tener con los calzoncillos.
El uso de la palabra gayumbo con este significado data del siglo XIX al menos:
No hay sino recordar los tiempos en que Puerto Real solo ofrecia por San Juan y San Pedro sus candeladas, sus gayumbos y tal cual baile improvisado.
La Moda elegante (Cádiz). 7/6/1863, página 8.
Y escrito como gallumbos hay artículos con este significado de la palabra de hasta 1844.
Resumiendo: tenemos dos acepciones de la palabra (como planta y como toro) usadas en el siglo XIX, y su acepción como "calzoncillos" de principios del siglo XX. Ignoro cuál de las dos fue el origen (si es que alguna lo fue) de esta última, aunque desde luego la explicación de que se usaba la planta de los gayumbos como desodorante natural para los gayumbos es plausible. La lástima es que no he encontrado ningún texto que lo confirme o que haga mención a dicha práctica.
