I'll second Mr. Sharp's recommendation of writing harmonies at the piano. That's pretty much what I always do. In fact, I keep a condenser mic wired up at my piano so I can record the harmonies as soon as I figure them out.
I am not the expert on how to write harmonies, but I generally try to come up with 1 or 2 parts that are higher in pitch than the lead, and 1 or 2 lower (depending on how dense I want the harmonies). Rather than writing specific harmonies (based on intervals), I generally think of it as writing counter-point melodies (i.e.-come up with a different melody in the same key that doesn't clash with the lead).
Don't limit yourself to basic intervals or just notes in the chord you are singing over. Rather, explore the entire key. You may find that the minor 7th really has a cool sound, for example.