I love playing along with songs. When I was first getting started I would randomly hunt and peck for notes. Sometimes, I would hit a good note and that was thrilling. Mostly, it wasn't. But the more I did it the better I got at it. So, continuing to play along with recordings will help you get better, even if that is all you do.
Learning a little theory will help. Many songs are organized around basic scales. The scale will help determine which notes are in the melody and which chords are in the harmony. Certain notes and chords are often found together, so learning those groups of families of sounds will give you more clues. For example, if the song has a G chord in it, odds are, it will also have a D and a C chord.
You could learn this by studying theory, or you could learn it by studying lots of songs. Learning theory is the longer, systematic, and thorough way; learning a bunch of songs and recognizing the patterns (like G chords often go with D chords) is quicker, but less systematic and thorough. Older lesson books, like the Mel Bay books were built on the model of slowly acquiring knowledge of the basic keys, scales, and chord relationships. This is also the kind of thing that students cover in high school and freshman theory courses. You could learn this by working through a theory book or going to one of many online theory sites. A good teacher could help you learn tunes while explaining the theoretical information in each tune. Or, if you play along with records enough, you will probably get a good enough grasp of the theory principles at work in the music that you like. Whatever approach you take, pay attention to patterns. Most music is built on certain patterns.
One thing to bear in mind - music theory is like the rules of a particular game. Understanding the theory implicit in the music of Bach is different from understanding the theory implicit in Kurt Cobain or the blues. It would probably be most helpful to work with a theory book or teacher who shares your musical tastes and interests.