I often learn melodies (and all the rest) from printed music--it may be my only source. It shouldn't be that hard for anyone: the notation is entirely scale oriented. Whatever the key, the key signature takes care of applying the requisite sharps and flats, so once you figure out the starting note for the key (the tonic), going up or down lines and spaces is just walking the scale. Keeping track of the sharps and flats is harder when you're playing an instrument, but when you're singing, you're dealing with a smooth, regular continuum of pitches--each key is as easy as any other (provided it fits your range well), and we hear and interpret music relatively anyway, rather than in specific keys. Ask anyone to sing "Happy Birthday" starting on a given note, and most people can do it easily, but ask them what note or key that was, and few people can do better than get in the ball park, while most won't have a clue.

I may have trouble sight-reading on the fly, such as when a song uses a lot of chromatic notes outside the scale, or when there are leaps in the melody, but otherwise it's pretty easy. When I lose my local frame of reference or an interval just isn't "clicking", I just return to a nearby tonic and walk the scale up or down. Maybe that's where people have trouble: they can't easily sing the tonic of their key on demand, or bring it to mind for comparison.

Lead sheets and sheet music can help me more than hearing recordings, though I mostly do learn songs from recordings--cross-checking against sheet music, if available, to see what liberties were taken. Good singers often dress up lines in wonderful ways, but more often I hear singers opt for simplifications that strip life from how a song was written. I'll spare you my rant on how the "folk process" erodes rather than improves well-crafted songs--the tyranny of mediocrity.

For those having trouble, I recommend interval ear training, that is, learning to sing and recognize each interval, both upward and downward.