'How did they know?' Maybe they didn't !
Notice a couple of things. The sequence moves in 4ths, which is a common enough way. Think ii-V-I, used a lot in jazz, but also in lots of other music. The ii sounds like it wants to go to V (1 4th up), which then wants to go to I (another 4th up). So the 4th bar (Fmaj7) would move naturally to B&flat(maj7), and if the composer wanted to write Ds there, they would fit (M3).
Also, virtually every bar has a note or notes that are chord tones. So whatever notes go in a particular bar, generally speaking, they will be found within the prevailing chord. Music tends to work that way. Most tunes can be seen to have harmonies that reflect notes, or notes from the harmonies are found in the bar.
As far as 'how do they know?' goes, most composers have either the melody or the harmony in their heads while writing, and sometimes both pop out simultaneously. Mainly due to experience of what goes with what.
Pretty well any piece can be re-harmonised - let's say in key F (ATTYA), the note F itself works over an F chord, a B♭ chord, a Dm chord, a Gm7 chord, to name a few. And, with particular reference to jazz, any set of chords can have competely different melodies played over them. It's what we do! Although it's hardly a new phenomenon - it happened in Bach's day, and well before!