In the books they are just regular horses, that was why the flooding of the river was useful, it removed the Black Riders' means of transportation. One would presume that in the movies they were the same.
The horses were killed in the flood, but not the riders:
'And is that the end of the Black Riders?' asked Frodo.'No,' said Gandalf.'Their horses must have perished, and without them they are crippled. But the Ringwraiths themselves cannot be so easily destroyed...
Three of the black horses had been found at once drowned in the flooded Ford. On the rocks of the rapids below it searchers discovered the bodies of five more, and also a long black cloak, slashed and tattered.
They were bred and trained to serve their masters, and were perhaps evil, but they were "regular" horses, not magical.
In addition to what SSummer added about Sauron stealing horses from Rohan, it is important to note that Tolkien animals and indeed some plants are usually more than they seem. So when I say that the horses were "just regular horses" what I mean is that they aren't any more fantastical in and of themselves than the other horses in the books. They are certainly fantastical when compared to horses from our world.
Just to add to the answer, here is another passage from The Fellowship of the Ring that again clarifies what the horses were:
'...But why could we all see their horses?'
'Because they are real horses; just as the black robes are real robes that they wear to give shape to their nothingness when they have dealings with the living.'
'Then why do these black hoses endure such riders? All other animals are terrified when they draw near, even the elf-horse of Glorfindel. The dogs howl and the geese scream at them.'
'Because these horses are born and bred to the service of the Dark Lord in Mordor. Not all his servants and chattels are wraiths! There are orcs and trolls, there are wargs and werewolves; and there have been and still are many Men, warriors and kings, that walk alive under the Sun, and yet are under his sway. And there number is growing daily.'
