When I learnt Portuguese onde for "where", I already knew Spanish donde (and ¿dónde?) with the same meaning. This is confusing, because Portuguese also has a word donde, but it means "from where" ("whence" in older kinds of English), and corresponds to Spanish de donde (or ¿de dónde?, if used interrogatively).
Because Portuguese is known for losing consonants (cf. cielo, céu; buena, boa; sonar, soar; lleno, cheio) I assumed the original form must have been donde, and Portuguese lost the initial d.
But it is not so: Portuguese onde comes from Latin unde! That word did not mean ‘where’, but ‘whence’. ‘Where’ is ubi in Latin (cognate with French où, Italian ove, and Old-Occitan, Old-Spanish and Old-Portuguese o). So we have:
|whence||de donde||de onde, donde||de unde||unde|
So it seems that first the notion that Latin unde semantically included the idea of ‘from’ got lost. This must have happened early, because Romanian has it too.
Then de was added in Spanish, incorporated into the word, and its meaning forgotten again. Then to express ‘from where’, de was added a second time!
The alternative possibility, that the d of Spanish donde was added to make the word easier to pronounce, seems unlikely because ‘wave’ is onda in both Spanish and Portuguese, from Latin unda.