Singing harmony is just a skill. It can certainly be learned, like any other skill.

You didn't specify what type of context you're planning on singing harmony in (a choir? a home studio? a band? just driving around in the car?), nor what your current level of musical knowledge/experience is (Do you play any instruments? Can you read music? Do you know any music theory? Have you done any ear training?). Both of these factors will influence the answer to some degree. But here are some tips that might help you:

Ear training is a good place to start. There are, in fact, many posts on this site that discuss ear training. Here's a few to get you started:

• How can I train my ear for music?
• What are the most effective ear training methods?
• Are there any games useful for ear training?

Sing frequently... They say practice makes perfect. You should try singing harmony as often as you can, and at every opportunity you get. This will give you lots of chance to experiment with trying things in different ways. This is probably the most important thing you can do.

With other people... If you haven't already, try finding someone else who sings a harmony part well, and try to follow their lead. Listen to what they're doing and try to match what they do. This is useful in a choir setting, where you've got other people around singing the same part.

From written music... If you can at all, try singing the part from written music notation. This will allow you to look at the notes and form a correlation between the graphical notes on the page, and the audible notes that you hear. You aren't listening for absolute notes ("that's a D"), so much as for relative contours ("this part goes up, then jumps down low") and general ranges ("notes above this line feel high to me").

While actively listening. Whenever you have time to listen to music, do not just listen passively, to the superficial sound of the music. Really listen "deeply" or "actively" -- try to hear all the intricate details in the music. What is the bass line doing? What is the rhythm. Are the any countermelodies or little riffs? If you can do this while reading through the written music (as above), so much the better. That little countermelody that you just heard... stop the recording and try to sing it back without the melody. This may involve rewinding and replaying several times.

Now, if you're singing material for which you don't have the score, than listening is even more super-important, because you will have to learn to improvise a harmony. This isn't as hard as it sounds, but it depends on being very aware of what is going on in the music around you.

Find the tonic (key note) and the dominant (fifth) If you can find the 1st and 5th notes of the scale you're in (also called the tonic and dominant, or 'do' and 'so'), you can often use those notes as anchor points in your harmony, as they tend to sound the most stable, and be the easiest to find. All the other notes in the scale (except one) are within a step of these two notes, so if you can find one, and it isn't the right note, chances are good that you can go up or down a step to find a good note.

Practice with an instrument First try playing some random series of notes on an instrument (probably not a woodwind or brass, and stay in a single key, and move stepwise), and try singing in unison with it. Then try singing in parallel thirds, fourths, fifths, and sixths. To do this, play the starting note of the instrument part (such as a C), then play the starting note of the singing part (such as an E), to get it in your head, then while singing this pitch, go back and play the C. Do this a couple of times. Now move your voice, and the note on the instrument, each up one scale degree (playing C goes to D, while singing E goes to F). Then bring them both back down one. Try repeating that a couple of times. Then try bringing them down one and back up. Repeat both of those a few times until you're comfortable. Then try expanding your range beyond that, scalewise at first, then gradually by small intervals. For a really Medieval Church sound, try doing it with fifths.

No single melody is likely to be harmonized completely in a single interval, but by doing this exercise, you're getting used to the feel of singing something other than what's being played, and getting used to the sound of consonant intervals. This ties back in with the ear training, and with learning music theory should you happen to do so (theory's not strictly necessary to sing harmony, but it certainly doesn't hurt, especially just the basics).