Ive played theremin for all of four days, so I’ll answer based on my vocal/guitar background. I learned basically the same way as Dewster’s old roommate, high school chorus provided a lot of ear training while singing harmony parts in duos and trios without anyone to match gave part independence and the opportunity to improvise. I’d listen closely to harmonies and try to pick them out. I found the development of my harmonic ear largely followed the development of harmony in western music, I.E. first I tended towards parallel fifths and pedal tones, then I learned how to harmonize in thirds/sixths (which is actually the same thing since a major third up from the melody is the same note (in a higher octave) as a minor sixth down and a minor third up is the same note (in a higher octave) as a major sixth down). This one remains my go to harmony when first figuring out a harmony and is very common in popular music (I’ll describe it more below). After that, I learned how to harmonize other chord tones (providing the 7th or an extension to the chord), often the role of the baritone in a barbershop quartet, which takes practice and is generally best when there’s a lot of other harmonic content so that you can create in-tune dissonance. To start, I’d recommend practicing keeping parallel fifths in tune and learning how to do the third/sixth harmony (which can be done by learning to recognize it in songs and singing along with the harmony vocal).
From a theory perspective, the trick to the third/sixth harmony approach is to be conscious of where the melody is in the chord and to play the major/minor interval based on that. So if you are playing a major key song and the melody note is the root, you want to play a major third above (or minor sixth below) the note. If the melody moves to the third, you then want to play a minor third above (major sixth below) the note, which puts you on the fifth of the chord (you could also switch places with the melody and play the root in this case). If you stayed in parallel major/minor thirds all the time you’d go out of key (in the last example, if you stayed in parallel thirds and the chord didn’t change you’d end up playing a dissonant interval in the chord, which could be cool, but has to be very intentional). A good, clear example of this harmony is the harmony in the last verse of the Beatles “All My Loving,” which I think follows this form the whole way through.
After you get good at parallel harmonies, try practicing harmonies that mirror the melody (the melody goes up, you go down, which can be super cool if you meet in the middle and then cross voices so a high harmony becomes low or vice versa). Then start getting really crazy and start doing different rhythms from the melody (changing note at half the frequency as the melody is a good gateway into this). Then learn counterpoint and become a baroque composer (note, I’ve skipped this last step).
The world of harmony is very fun, enjoy! Now I’ll go back to picking out the worlds easiest theremin melodies. I’ve almost got twinkle twinkle little star down, if you pretend not to notice the drifting key!