Yeah it's just a matter of training your ear to recognize what the melody is doing. When you're able to tell what note (within the key) the melody is, you can put your theoretical knowledge to work and choose different harmonies.
For instance, let's say the melody is the 3rd of a major chord. Once you're able to recognize this, you can then say "oh ok, he's singing the 3rd; I can sing the 5th or the root, etc. (There's other choices, but I'm just simplifying for now.)
It would be good to practice along with slow songs that have really long or repeated notes in them. "In My Room" by the Beach Boys is a good one, for instance.
Practice playing a G chord, for example, and then sing the root (G) for a measure. Then go up to the 3rd (B) for a measure, then up to the 5th (D), then up to the major 7th (F#). Record yourself doing this, then play it back and practice harmonizing a 3rd above each note. Over the G note, sing a B, over the B note sing a D, over the D, sing an F#, over the F# sing an A. Once you get this down, start adding chords to the progression.
You might add a C chord, and the melody over that chord could go: G, C, E, G. And you could harmonize that melody with C, E, G, C or something like that. These are of course are very clinical examples, and real melodies are obviously much more complex. But it's a good way to get started.
Other than that, just practice trying to sing harmony to anything that you hear. You'll usually be good by singing up a 3rd or 4th, depending on the chord/melody relationship.
good luck