I could not harmonizer by ear--and I tried for years to do it!- It occurred to me one day that, when I played my guitar accompaniement to a song, that I was actually playing several harmony lines at the same time--now, I basically just pick a note out of the guitar part(as long as it's not the melody note!) and follow it though the changes til I get to the end--you do have to think about where you're going to end up, in relation to the melody voice--In music theory, the melody would be thought of as the "salient line" and the harmony as the "recessive line"--the names tell you what you need to know: that your harmony shouldn't overshadow the melody! So a good rule of thumb is to keep it from moving around too much--
You could visualize this as keeping on a straight line (on a single pitch) but 'curving" a little to accomodate each chord change--
Here is a good tip--it doesn't hurt to "rest", particularly on pick-up notes and in other places where the melody is particularly busy, and to fall back in when it reaches a sustained note--