Okay, I’ll explain.
There are things called chord tones; these are just notes from whatever chord is being played in any given measure or beat. For example, the chord C major includes the notes C, E and G; those are chord tones. The chord G7 includes the notes G, B, D, and F; those are chord tones.
When harmonizing a melody (or with a melody vocally), you want to be playing/singing chord tones when chord tones are being played/sung. There are exceptions to this rule, but for now lets say this is written in stone.
As you might have guessed, there are notes that are sung/played that are not chord tones. These notes tend to be notes that pass from one chord tone to another (passing tones) or notes that move away from a chord tone (by 1/2 step or whole step) and back to the same chord tone (neighbor tones).
As long as you follow what the melody is doing (chord tone, passing tone or neighbor tone) with your harmony, you are bound to be right 75% of the time. Why not 100%? because depending on the chord being played at the moment, following the melody note for note with a harmony is much more complex than just parallel movement. I will say that singing/playing chord tones is almost always a safe bet no matter what the melody is doing. Again a chord tone is just a note from the chord that is playing at any given moment or beat.
Consider that tunes don’t always stay in the key of the first or last measure (or key signature). As in this topic, the tune changes to the key of Bb for a few measures. That means that the passing tones and neighbor tones will change along with the scale from the key within those measures (or beats). Ya gotta follow the tonality from any given moment.
Finally, you should also consider that the ear likes certain harmonizing notes better than others depending on the style of music being played. Generally, the ear finds thirds and sixths to be pleasing and perfect fourths and perfect fifths hollow sounding or stark. However, in 3 or more part harmony, 5ths and 4ths are inevitable sometimes and do not need to be avoided completely even in 2 part harmony. It just depends on the sound you are looking for.
So that was the dry basics of harmonizing a melody. There is so much more, but most folks can hear much of what they like just by following these simple rules. Take them with a grain of salt and use them as tools (not rules) to quickly find harmonies you like.