We first learn what the Black Riders are long before we see one. Gandalf tells Frodo, "Nine [Rings of Power, Sauron] gave to Mortal Men, proud and great, and so ensnared them. Long ago they fell under the dominion of the One, and they became Ringwraiths, shadows under his great Shadow, his most terrible servants" (1.2.84).
(Click the infographic to download.)
These nine kings have fallen under the most extreme version of Ring possession: their Rings have actually consumed them, so they no longer have human form. Without their horses and their cloaks, they would have no shape at all (which is horrifying – they could be anywhere and we wouldn’t even spot them!). These Nine are the Black Riders who come to threaten Frodo in the Shire. But the Hobbits don't immediately make that connection. All they realize is that these Black Riders appear extremely unpleasant. We know that they are Sauron's "most terrible servants."
As Frodo sets off from the Shire with Sam, Merry, and Pippin, they reach the forested area of Woody End. There, they get their first glimpse of a Black Rider, a cloaked figure riding a black horse. Frodo and the Hobbits hide off the road because Frodo does not want to be spotted. But when the Black Rider draws near, Frodo is filled with a "sudden unreasoning fear of discovery" (1.3.83), and he almost puts the Ring on. Only remembering Gandalf's warning against using the Ring saves Frodo from putting it on in the presence of the Rider.
The Hobbits notice that the Rider seems to be sniffing for Frodo, almost as though he can smell Frodo like an animal. Indeed, Aragorn later confirms that the Riders can't see the way people can, but their horses can see, and "at all times they smell the blood of living things, desiring and hating it" (1.11.116). Maybe the Rider can smell Frodo's blood and/or sense the Ring, but in any case, he goes away eventually (this time).
The Black Riders continue to hover threateningly in the background right up until Aragorn leads Merry, Sam, Pippin, and Frodo to Weathertop. (Frankly, we are not denying Aragorn’s fighting skills, but it seems a little silly to bring the Ringbearer to a giant hill that stands out in the middle of a flat plain. Weathertop is hard to miss, after all. No wonder the Black Riders find them without too much trouble.)
In the presence of the Black Riders, Frodo cannot stop himself from putting on the Ring. As soon as Frodo slips on the Ring, he becomes visible to the Riders. Their leader (the Lord of the Nazgûl) stabs Frodo in the shoulder. Aragorn chases the rest of the Wraiths back and does his best to treat Frodo. Gandalf later explains that the knife that stabbed Frodo was a Morgul-knife, which can turn its victims into "a wraith under the dominion of the dominion of the Dark Lord" (2.1.38). Luckily, Frodo survives the attack. Unluckily, his injury makes him even more vulnerable to the Ringwraiths.
Since the Hobbits don't recognize the Black Riders (and Gildor Inglorion refuses to fill Frodo in, "lest terror should keep [him] from [his] journey" [1.3.159]), we get the suspense of watching our heroes trying to evade an enemy they do not understand. And Gildor's mysterious announcement that he does "not think it is for [him] to say more about them" (1.3.159) only makes us more interested in these strange figures. How can they be so dangerous that a High Elf refuses even to talk about them with Frodo?
What makes the Ringwraiths even more scary is that they are shapeless. We cannot picture them in the detail that we can picture, say, Gollum. How do you defeat a formless spirit? How can you ever stop such a thing from coming after you? The power of the Ringwraiths is so strong that it almost beats Frodo even before he has really started on his quest with the Fellowship. The fact that the Ringwraiths are only servants of Frodo's real enemy demonstrates to the reader exactly how tall an order finishing this Ring quest is truly going to be for him.
We don't know much about the Witch-lord of Angmar in The Fellowship of the Ring. We do know that the Hobbits sent a few archers to help fight him in battle at Fornost a while back. That war was the end of the North Kingdom of Arnor (and the end of the line of the high kings at Fornost, to whom the Hobbits were loyal before the line died out). That was also around a thousand years ago. So the Witch-king of Angmar must be long dead. Or – is he?
We later find out that the Witch-lord of Angmar (a.k.a. the Witch-king of Angmar in the Appendices of The Return of the King) is also the leader of the Nine, the Ringwraiths who are Sauron's most deadly followers. They were once great kings of men, but they were corrupted by the Rings of Power that Sauron gave them. Now, they live a cursed half-life under Sauron's power. In fact, it is the Witch-lord of Angmar who stabs Frodo with his Morgul-knife at Weathertop (see Book 1, Chapter 11). Frodo realizes this later, as he watches the Lord of the Nazgûl mustering his troops in The Two Towers Book 4, Chapter 8.
When Frodo and the Hobbits are hanging around the Old Forest with Tom Bombadil, he tells them of "the evil king of Carn Dûm in the Land of Angmar" (1.8.64). So, the soldiers who fell fighting the Witch-king are those buried in the Barrow-downs near Tom Bombadil's cottage. He comes back to lead an army of wraiths from Minas Morgul in The Two Towers Book 4, Chapter 8; he is also leading the host of Mordor against Osgiliath and Faramir in The Return of the King Book 5, Chapter 4. Keep your eye out for him.