In the interrogation scene with Agent Smith after they apprehend him at his job, Smith says
As you can see we've had our eye on you for some time now, mr Anderson. It seems that you've been living two lives. In one life you're Thomas A. Anderson, program writer for a respectable software company. You have a social security number, you pay your taxes, and you... help your landlady carry out her garbage.
The other life is lived in computers. Where you go by the hacker alias "Neo" and are guilty of virtually every computer crime we have a law for.
Earlier, in the club where Neo meets Trinity for the first time, Neo says
Trinity? The Trinity? That cracked the IRS keybase?
It seems that Morpheus has a habit of keeping an eye on the hacker scene inside the Matrix.
From the script, lines that didn't make it into the film:
MORPHEUS: Let me tell you why you are here. You are here because you have the gift.
NEO What gift?
MORPHEUS: I've watched you, Neo. You do not use a computer like a tool. You use it like it was part of yourself. What you can do inside a computer is not normal. I know. I've seen it. What you do is magic.
NEO It's not magic.
MORPHEUS: But it is, Neo. It is. How else would you describe what has been happening to you?
Since Neo is presented as a pretty notorious computer criminal, that is likely how Morpheus first heard of him, also corroborated by the fact that they never refer to him as anything other than his online alias.
As for how he knew Neo was the One, once he came to his attention, perhaps he also knew about Trinity's prophecy from the Oracle, that she would fall in love with The One, and noticed, as Cypher did, that Trinity likes looking at Neo. Or, maybe he just had a feeling, which would not at all be out of character for him. He takes a lot of things on faith, and the rest of his crew doesn't seem to have any reliable reason to believe that Neo is The One, other than Morpheus' word.
A further possibility builds on a theory that I personally think is heavily implied, but is never outright stated, regarding The Matrix and how the Red Pill People are able to bend it to their will. The act of skirting the rules, jumping long distances and doing super fast martial arts and dodging bullets, is a form of hacking. It's hacking that uses the interface provided by The Matrix for interacting with the simulation, and is only performed on a subconscious level for most Red Pills, with the exception of Neo at the end of the first movie where he gains the ability to see the Matrix interface for what it is and more directly exploit its weaknesses. As such, seeing as how that ability was what defined The One in the first movie, it's not unfeasible that Morpheus was able to glean that Neo was capable of that level of Matrix hacking by observing his simulated Blue Pill hacking.
You like him, don't you? You like watching him.
They didn't know each other... only Morpheus (and the crew) knew Neo. :)