Question: To all the people with good ears:

when you're figuring out a melody by ear, are you listening to the sequence of notes and figuring out where each note sits relative to the root of the key?  

Or are you figuring out what the next note is by the interval from the last note?

Answer: 
You have to learn motifs and intervals. (Make your self a list of the most usual like:
so-mi, so-la-so-mi, do-re-mi-do, do-re-mi-fa-so, so-do, so-do-mi, so-la-ti-do, do-do-ti-do, do-ti-la-ti-do etc. etc. and then you'll recognize them in a melody. There are lots of identical turns and formulas in folk or pop songs.

You can make (also when listening by ear) a harmonic analysis like a piano chord reduction, filtering out the triad (arpeggios) and add the other tones as change notes, passing tones and approach notes.

And you won't ask which method we prefer. Everyone uses both and not only these two. You can listen to the base line, the melody, the cadences and sequences and the transposed motifs. All are playing a role, all of them are helpful.

So start training scales, intervals, triads and 7th chords with their resolution like: so-ti-re-fa ->mi-do, by singing, writing, playing, listening.

do-re-do-mi-do-fa ... or do-mi-re-fa-mi-so (all combinations of intervals and sequences. That's what solfege is. Search for solfeggios and warming ups, also for piano etudes for beginners.
If you have perfect pitch, congratulations! None of the following probably applies.

If you have good but not perfect pitch, you can probably get by...if the key and the number of voices, counterpoint, and harmony isn't that complicated. I did this in my first music theory class when we had to transcribe 2-3 moving lines, and it stunted my growth when we started getting lots of chromaticisms, secondary dominants, and hard key signatures.

For mere mortals like myself, the "correct" way according to my college professors is by training your relative pitch, or recognizing intervals between two notes. (It's been some time since I left college, so I may have forgotten some of the finer-grained details).

With good knowledge of what intervals sound like, you can do the following, given the lowest note of a chord:

* Figure out all intervals above the lowest note
* Figure out the lowest of the next chord in relation to the current note

This should theoretically allow you to transpose any piece of music, but it's really slow.

You can combine it with the following shortcuts to speed things up:

* Use knowledge of tonality (major, minor, types of seventh, etc.) to identify the quality of the chord.
* Use music theory to rule out unlikely chords in the chord progression/identify non-chord tones and chromaticisms if you are given the chord progression
* Use knowledge of inversions + the location of certain intervals to quickly find the root (e.g., if you hear a 2nd in the lowest 2 notes of a 7th chord, it's probably in 3rd inversion)