Is it through chord progressions?
Generally, if melody notes have a short duration then they don’t have to be part of the current chord because even if the melody notes clash with the chord, it’s only for a brief moment. Short notes in this example are 8th notes. You’ll notice that the longer notes usually tend to be chord notes. If longer notes (quarter notes, half notes, whole notes) are NOT chord notes, then it may produce too much dissonance.
A good melody is a combination of some dissonance and consonance. Also, well-written melodies tend to use a mainly smooth steps with jumps thrown in from time to time. A melody that has not jumps (3rd or more) from note to note may be boring. A melody that has too many jumps is not compelling because it lacks “singability”.
Lastly, most melody notes should be from the scale. The Edim chord is outside of the scale. He’s using modal interchange and he borrows that chord from the tonic minor (D minor).
Anyways, hopefully this gives you some insight into how these melodies came about.