They seem to have been bred from earlier Ages. They had to feathers or quills and they had vast hide between their fingers, which they used for pinions. They also stank. It is never stated that all the Nazgûl rode fell pterosaur-like creatures, but some infer that they did so.
The fell beast attacked and eventually killed Snowmane, Théoden's horse. The horse fell on Théoden, crushing him. Dernhelm (who revealed herself as Éowyn) defended the dying Théoden, and challenged and killed the beast.
Tolkien actually only used the name "fell beast" as a descriptor and not an actual name. ("Fell" in this sense is an archaic English word meaning "cruel", "evil" or "lethal".) However, since this creature lacked any real name, "fell beast" is often used to refer to it.
In Letter 100, Tolkien referred to them as Nazgûl-birds.
Portrayal in Adaptations
In Ralph Bakshi's 1978 animated version of The Lord of the Rings, one of the Nazgûl (possibly the Witch-king, for he carries a mace), is shown riding a fell beast. However, Bakshi's film only covers events up to the Battle of the Hornburg, so that is the last we see of the fell beasts and their riders.
In Peter Jackson's The Lord of the Rings, the fell beasts are depicted as more Dragon-like and serpentine creatures, i.e. their heads appear more like a snake's and they don't have beaks, leading to the common misconception that they are dragons in the books; Tolkien definitely meant a pterosaur-like creature, as shown in the quote above. This depiction came largely from John Howe's influence.
Also, they are much larger than is implied in the books, where they are essentially used as light observation planes. In the movies, they are used for attack much more often, with the Nazgûl usually swooping down and screeching, making the defenders at the gate of Minas Tirith run away, leaving Gandalf alone to face the Witch-king as he enters.
Although on screen the films never make this mistake, sometimes cast or crew members (Lawrence Makoare and Richard Taylor most notably) on the commentary tracks and the documentaries refer to the fell beast as a Nazgûl; this is incorrect. The fell beast is the creature that the nine Nazgûl ride, and the mistake probably arose because fell beasts are always seen with a Nazgûl atop them.