I asked something a little bit similar in the past.
I am mainly thinking of Paul Simon for this question, especially in the song "The sound of silence."
How does Paul think of which notes to go with what notes Art is singing? Is he playing notes which he believes sound right?
All the notes sung are harmonious with each other. They fit each other, they usually blend with the underlying chord - they are harmony.
As a very good guitarist, a person singing harmony to another will be listening to that person's vocal, but also to the guitar chords, which should contain most of what the harmoniser needs to work with. The intervals that go together nicely are thirds and sixths - inversions of each other, fourths and fifths, both of which can sound 'hard'. Not difficult hard, but not blending too harmoniously. But sometimes, to form a phrse that works against another's melody line, 4ths and 5ths are needed.
If you think if a basic major triad, there's a 3rd between 1 and 3,(C>E) another between 3 and 5,(E>G) and a 4th between 5 and 8.(G>C) The missing link is a 5th between 1 and 5 (C>G).
I mentioned good guitarist earlier. I've worked with several vocalists who play no instruments, but could harmonise perfectly, almost spontaneously, certainly with a little rehearsal. And I really don't know how! If I did, I'd bottle it and make a fortune! Certainly not great lessons or theory, just naturals. Like Simon and Garfunkel.
All that may be on the wrong tack, but related nevertheless. The notes played on guitar, in this case, all belong to certain chords which work in conjunction with others from the same key. The guitar is playing quasi arpeggios, made up from notes which constitute chords. These chords would have been established as the song was written. Maybe spontaneous, maybe blood, sweat and tears to produce a beautiful song. It could be that half way through, they wanted a particular note, and spent ages trying all sorts of ideas until the one we hear popped out.
As far as I am aware, the ability to sing or play notes that harmonize with a particular melody line is not something one consciously thinks about - but rather something that the musician or singer has a natural instinct for.
In other words, there is not a mental process that takes place where they think something like - "okay - the melody note is a C so I am going to play or sing a third above that which is an E so I will play or sing an E".
Certainly if you lacked the musical ear and instinct to just feel what note harmonizes with a given other note, you could painstakingly do the mathematical calculations and arrive at the harmony notes that will sound good (as described in Tim's accurate answer). But that is not what takes place with a gifted musician such as Paul Simon or Art Garfunkel.
Some folks have a natural innate ability to do certain artistic things such as artists who can paint amazing paintings with little or no schooling and musicians who rise to the top of the industry and crank out hit song after hit song. The ability to harmonize is something that some folks have and others do not. And some - like Paul Simon, have honed their natural ability to the highest level.
Musicians like Paul Simon, can harmonize any melody without much conscious thought. They go with their gut and sing or play what feels right in some deeper part of their conscious that mortal folks are not able to tap into.
Many talented musicians and vocalists don't need to know anything about music theory to be able to harmonize instinctively and effectively. Music theory only serves to tell us why it sounds good to our ear.
But I do believe that with practice, any musician with a basic ability to play by ear can improve their ability to play or sing harmony.
See the answers in this related question on Stack Exchange Music How to learn to sing harmony
