Often people think of music design as a mysterious, arcane art that can only be done by gifted geniuses who just have a special knack --- or, alternatively, that new music (improvisation or composition) can be made only by highly trained technical experts.  Not really!  There are only a few basic concepts that make it all come together, and here's what I've seen as a lifelong improviser:

1) Everything in normal "tonal" music is built out of a diatonic (do-re-mi) scale: seven scale steps in an octave, and nothing more.  In elementary school music or elsewhere I hope you've gotten the chance to hear that that scale is a "whole step, whole step, half step, whole step, whole step, whole step, half step," easily seen in the key of C on the piano.

2) The usual melody is built out of notes from that scale --- period.  That's where it comes from!  So when you're working with finding notes for a tune, you have seven basic note options you're drawing from, and that's all!

3) All the major and minor chords used for harmonizing the usual melody are also built out of the six scale steps --- just that!  The chord built from the first scale step is made up from the first, third, and fifth scale steps; the chord built from the second scale step is 2, 4, 6.  See the pattern?  Every other note above the scale step makes up the chord it's the root of.  That's all!

4) To decide on a harmony that sounds nice with a particular melody note, choose a chord in which it's either the bottom note, middle note, or top note --- three good chords to choose from!  (In the key of C, for example, if the melody note is an E, it's the bottom of the E minor chord, the middle of the C major chord, and the top of the A minor chord --- so each of those chords is a contender for your harmony choice.)

5) To improvise a new part that isn't the melody, you keep track of what the scale is (usually major or minor in a certain key), what the tune is, what chords have been chosen to harmonize that tune, and then look for other notes that aren't the melody.  That's where special parts come from.

6) All this is happening as you go through time, so you need to keep track of how it's moving along.  Special new parts relate to the scale, melody, and chords as they progress through time.  Tick, tick, tick!

These are the main things to keep in mind as you experiment with musical ideas to work with a melody.  They're  not a mystery or a deeply academic thing --- and they're worth trying!