Take some existing simple melodies that you know (like nursery rhymes and hymn tunes) and try to work out by ear what the chords are. They are probably all chords I, IV, V, and maybe VI of the key. For example, in C major: I is C major, IV is F major, V is G major (often with an added 7th), VI is A minor.
When you think you've got it right, look up the `official' chords in a book or online (be careful online, I've found some hilariously wrong chords for pop songs).
Developing your ear is the most important thing. `Rules' for harmony just summarise what many people have thought sounds good. Theory also provides a language for talking about what the music is doing (whether or not the music is conventional).
Work the other way around too: take a chord progression (whether from an existing song, or of your own creation), and improvise singing a melody over the top. The singing is important because it forces you to just use the natural notes that come into your head against each chord.
Also, investigate different notes against a given chord. While just keeping on playing the same chord, taking each of the twelve chromatic notes in turn, play it over the chord: does it sound `resolved' or `normal', or `unresolved' / `weird' / `tense', if the latter try using it in a melodic phrase between two `normal' sounding notes.
The chord for a given bit of melody often contains most or all of the melody notes. It often contains all of the stronger notes in the melody. A melody note can be `stronger' by being on a strong beat, by lasting longer, by being first or last in a phrase, etc.
Although, in a given key, every chord contains all the notes of the scale. For example, in C major, chord I fully extended is: C (root), E (major third), G (perfect fifth), B (major seventh), D (major ninth), F (perfect eleventh), A (major thirteenth). But that's all the notes of the scale, just organised in a particular way (in scale-wise thirds, starting on C). So any bit of a C major melody contains `only' notes from a (fully extended) C major chord. (Fully extending the C major chord in another key which contains it will give different extended notes, for example, in G major, the C major chord is chord IV and will have F# as the (augmented or sharp) eleventh.)
But each note of the scale has a different `sound' or `meaning' in the context of a given chord. A melody using Cs, Es and Gs over a C major chord will sound `grounded' and `normal'. A melody using Ds, Fs and As over a C major chord will sound `jazzy' or `floaty'. A melody using Cs, Es and Gs over a Bb major chord will sound `jazzy' or `floaty. A melody using Ds, Fs and As over a D minor chord will sound `grounded' and 'normal'.
But you can't look at each part of the melody and a chord for it in isolation. You probably want the chord progression on its own to have some sense to it: to feel like its going somewhere, telling a story, sometimes unsurprising, sometimes surprising.
Different styles of music harmonise their melodies in different ways. A hymn tune, versus a jazz bebop tune, versus a Joni Mitchell song. Within the same style, different harmonisations are possible. E.g. here is Chick Corea reharmonising his own Spain: https://www.youtube.com/watch?v=XsQRFgU2fz4 .