De means "of", and nada means "nothing", so why, when put together, are they used in response to Gracias?
According to DLE in de nada it's a polite answer to thanks being given to somebody.
Basically it's kind of equivalent to it was nothing/think nothing of it/no problem/don't mention it.
In Spanish you can also say no fue nada (and in that sense that sounds more "complete"), por nada, no hay problema; so basically de nada and the other variants are the current short way of saying no hay de qué dar las gracias or no hay por qué dar las gracias.
In English we say:
It was nothing
Don't mention it
Don't worry about it
All as very casual responses to "Thank you"
In Spanish I would use "de nada" in the same environment. With friends / family, etc..
If I were entering a classy restaurant and held the door for someone who responded with "muchos Gracias" then I would reply "es un placer" (it's a pleasure).
American English is famous for responding to thanks with an acknowledgment that something indeed was done: "You're welcome" (yes, I did you a favor, and I accept your thanks). Virtually all other European language respond to thanks with a denial that anything significant was done: "de nada," "It was nothing," "de rien," "det var ingenting," etc. "You're welcome" is "heard" as an Americanism in British English. And even Americans seem to be moving increasingly to the denial model: "no problem," "no worries," etc.
In Spanish, the term "de nada" means "[something] of little importance or value". The expression "cosa de nada" has been used for centuries:
—Bien puede vuestra merced, señor, concederle el don que pide, que no es cosa de nada: solo es matar a un gigantazo, y esta que lo pide es la alta princesa Micomicona, reina del gran reino Micomicón de Etiopia.
Miguel de Cervantes Saavedra, "El ingenioso hidalgo don Quijote de la Mancha", 1605 (España).
Searching in the CORDE you can find some matches of the expression used in contexts implying asking for a favour:
—Pues verá —dijo—, venía a ver si arreglábamos ahí un asuntillo, una cosa de nada.
José Manuel Caballero Bonald, "Dos días de setiembre", 1962 (España).
Or in contexts where the speaker means that something he/she has to do is in fact something very easy for him/her, so it has no value or importance:
—¡Cosa de nada! —como dijo Andrés respingando de gusto cuando las vio—. Descalzarme, remangar las perneras hasta los muslos y en un decir "Jesús", atracar un poco las vigas, halando del cabo del arpón; saltar encima de ellas, y con el palo que tengo escondido donde yo sé, bien cerca de aquí...
José María de Pereda, "Sotileza", 1885 - 1888 (España).
Funnily enough, I cannot find any text with this expression used as a return for "gracias", but it makes sense to think that the whole expression could be something like:
—Ha sido una cosa de nada.
Due to "de nada" being the most important part of the whole expression, the one remarking that the thing done has no value, it is the part that remains nowadays.
If we bring Portuguese into the mix it might shed some light into this whole question.
"Thank you!" = "Obrigado(a)!" > which literally means I am obliged or I now am obligated to repay your favor.
"You are welcome!" = "De nada" > I'm basically saying to that person who thanked me that it didn't cost me anything (effort or otherwise) so he/she doesn't owe me anything.