Well, in my opinion, first you have to KNOW your scales. I mean know how to play several different scales (at least diatonic major and minor, pentatonic major and minor and a couple modes...at least) across the fretboard.
This takes a lot of time. Not a day or week or month, but many months of practicing a few hours each day. This is what I did.
Next, you need to be able to at least comprehend melodies when you hear them. Be able to hum them or whistle them or emulate them on the guitar. I started with simple vocal melodies, simple guitar melodies and tv show theme songs...seriously.
Also, hearing Jeff Beck's "Blow by blow" album was a huge eye opener for me as far as melodic guitar playing.
For example:
Repetition is key with learning this stuff. You have to do it over and over and over and over...
Take that song that I played in that video. I listened to that song at least 10 times and got the basics drilled into my head before I ever attempted to learn it and play it. Once I started learning it, I sat in front of the computer w/ iTunes open and learned it the same way I learned stuff as a kid: played it over and over, learning it section by section until I could do a pretty good job emulating the original.
It takes time, dedication, study, self-motivation and patience.
