There's a lot to learn, and a lot of ways to learn it and practice it, so of course, there's no single answer that will give you the best way to learn, but here are several things to work towards, not necessarily in any particular order.
Active Listening
Always ask questions about whatever you are listening to. What instruments are playing? What is it's structure? Which instrument(s)/vocal(s) have the melody? Are there any notable countermelodies, or harmony parts? How does the bass line go? Does the melody (or any other line) have a lot of repeated notes (maybe with other notes in between), or does it jump all over the place? Where are the high parts, and the low parts? When are the notes moving faster or slower? Can you tell when chords sound like they are changing? When there's a chord change, does it sound like an expected change, or something out of left field? Does that chord sound like a sad minor chord or a happy major chord (that's a vast oversimplification of the difference between major and minor, but it gets the point across)?
Singing
Try singing various parts. Not just the melody, but the bass line, and any harmonies you hear. Learn to focus on different lines of music. By reproducing them vocally, you'll also be reproducing them in your head. Eventually, you can try cutting out the audible singing, and just sing along in your head.
Pitch Memory
You want to be able to hold on to one pitch while others are sounding, so that you can compare the two. Even better if you can imagine two pitches in your head, either simultaneously, or nearly so. Singing helps here as well, as it gives you a chance to actualize what you hear in your head.
Think about scales numerically
Every note in a scale can be represented by a number that describes where it is in the scale. It's much easier to hear that a notes is a "1", "5", "3", "7", or even "4♯" then it is to tell what the actual letter name is. If you can figure out the numbers, you can always translate back to letters once you figure out what the key is. Some people prefer solfege systems instead of numbers (do, re, me, etc...). That's fine too, if it works for you. I find numbers easier, but YMMV. The key is to avoid tying yourself to any specific notes -- most people don't have and can't learn absolute pitch, but relative pitch can be learned with a bit of practice. The converse of this is to make sure that you know all the notes in each scale, and what their numbers are, so that you can translate back and forth easily.
Landmark Pitches
The easiest pitch to determine is usually the "tonic" (the first note of the scale, '1', or 'do'). This is usually the note that the piece wants to end on, and even individual phrases (or pairs of phrases) will feel like they want to gravitate to it if they were to come to rest. I like to ask myself, if the song were to end right now, what note would I want it to end on. A second landmark pitch is the "dominant" (the fifth note of the scale, '5' or 'so'). The melody will often hover around this note, and it can sometimes be tricky to tell apart from the tonic, as it is also somewhat stable. I like to think of it as a sort of "plateau" that overlooks the tonic. It's a nice place to visit, but it isn't home.
Also, notice that with the exception of the third note of the scale, every other note is either the tonic or dominant, or is adjacent to the tonic or dominant. So if you can find the nearest landmark pitch, and determine whether you're above it, below it, or right on it, then you can figure out any note of the scale.
Unisons, and Directions
This is sort of obvious, but the first "interval" to learn to recognize is the unison, in other words, a repeated note. Most people can already do this. Assuming two notes aren't the same, you want to make sure that you can recognize which one is higher and which one is lower. Is the melodic line ascending or descending? Many people can already recognize this as well.
Scales
Mark already mentioned the importance of learning seconds (m2 and M2). These are notes that are considered adjacent in a (diatonic) scale. Starting out, I wouldn't even focus on learning the difference between them, just learn to recognize this adjacency. If two notes aren't adjacent, then you know its a bigger skip or leap. But if you can sing a scale of adjacent notes, then you can find any interval by singing a scale between the two notes and simply counting the number of scale degrees between them (including both endpoints). You won't be doing this in real-time, of course, but that's what practice is for. When you're starting out, you probably won't be recognizing much in real time anyway.
Intervals
With experience, you'll start to recognize larger intervals more readily. Initially, I'd stick with smaller intervals (3rds, 4ths, and 5ths), since they're both easier and more common. Maybe throw in octaves too, since they're faily easy to recognize. I also wouldn't worry about distinguishing major vs. minor intervals at first either. You can add in that distinction once you're comfortable determining the more general classes of intervals. Some people like to think of specific songs to help with varioius intervals, while others point out that this is tied to certain scale degrees. I occasionally like to use it as a way to double check my assumptions, but I rarely need to do so, and find it just as easy to sing (or imagine) a scale. It may be more helpful to a beginner, but YMMV of course.
Chunking
It may seem daunting to think of working through figuring out what every single note in a piece is, but it becomes easier once you are able to recognize certain gestures. It's often easy to pick out the last note of a phrase, then work backwards to figure out the series of notes that led up to it. For example, If you count five ascending notes which are all adjacent, and end on the dominant, then you know that the notes had to be 1, 2, 3, 4, 5. You can also simplify the music line by recognizing, then removing/ignoring small things like "neighbor notes" (where the pitch goes up a step than right back down, or vice versa), or bits of scale that ascend or descend by a third, which are easy to hear, and often serve to decorate an otherwise-sparse line. Some of this will involve becoming familiar with certain idioms that are used in various genres as well.
Chords
This is already long, so all I'm going to say about chords is that the tonic and dominant (especially dominant seventh) are usually the easiest to recognize, as is the difference between major and minor chords. Look for back and forth progressions between two chords. Also, if you can figure out the bass line, it is often playing the root (and less often, the third) of chords.
