First of all it takes a while to develop your ear and some pointed practice definitely helps. The short answer is use the tools at your disposal - usually your ear and maybe notation/tablature if you can find it for free/on the cheap.
With that said it is GREAT practice to transcribe the melody by ear (Using looping software ain't cheating in my book but others may disagree - ultimately our opinions don't matter, it's up to you!). There is very useful (free) software called Audacity that allows you to slow down and loop over parts of music - it won't sound great at lower speeds but you can slow it down without changing the pitch and pick out the notes. Do this enough (with progressively more difficult pieces) and you will develop a very good ear.
Now getting back to my earlier note on pointed practice, check out ear training (just google it, there are a million sites out there). If you already know basic theory (major sixth vs minor sixth, basic chord progressions, inversions etc) then all you have to do as take your theoretical knowledge and put some 'sounds' to it. If not, learn a bit so that you have some labels to stick on the different sounds you discover. Music theory isn't necessary but it can be very helpful.
The goal of ear training (at least for me) is so that when I hear something I:
a) know the relationship of notes
b) know how to play the notes relative to each other right off the bat (ideally in real time)
Some sample questions you can ask your self while you study is "What does a sixth sound like and how do I play it?" (I always think of the NBC jingle or the last 3 notes of the standard "Always"). "How about a fourth" (Heeere comes the bride). "A fifth?" (Crazy train - also flat sixth right after it) etc. Find melodies that really showcase a specific melodic jump and figure out what that jump is. Learn jumps up AND down and then learn to play that jump in a bunch of different places on the guitar neck. This will give you a great reference point for what an interval sounds like and how to play it. That way, when you hear one, you can just say "Oh man, that's a jump of a major seventh!".
Also sing along with it! Learn the melody in your voice (even if it's in a funny range) - if you can sing it, you can play it!
For classical guitar, don't be afraid to transpose - especially if it's your first piece! Why would I transcribe Moonlight Sonata in C# when I could transpose it down to A Minor and have some super-easy open bass strings to work with? (I may get attacked on that front so I will mention that I'm a jazz guy first and foremost and I'm treating this as an exercise in developing your ear, not paying proper homage to the great pieces of music, the likes of whichI could never ever ever do justice).
So to recap
1) Use tools at your disposal (namely your ear and sheet music - try it with your ear first and then go to the sheet music if that doesn't work out)
2) If you aren't satisfied with the tools at your disposal, develop your tools! Transcribe anything you can get your hands on from different styles! This Will increase your ear's power exponentially.
3) Learn how to play more melodies ( I didn't mention this before but I'm already a bit long winded here so I'll tack it onto the end)
4) Finally - learn to play the melody in different places on the neck - maybe think positionally at first but be willing to jump around so that you can put some nice voicings underneath.
You don't have to do this all at once (or any of it for that matter). This is just a road map of how I developed my ear! Pleasant playing!