There's obviously something magical about them. Is there any mention about their origin in the books or the tv show? or were they trained somewhere to acquire all the magic?
The origin of Red Priest(ess) is in "the network" of Red Temples. Some of Red Priest(ess) can use magic. But learning of magic is not a part of "standard" education for priest(ess) in Red Temples.
Melisandre's magical skills are due to her connection with Asshai. She looks like a well-educated witch who knows what she can and what she can't do. She knew that fire vision is often hard, she knew that the third shadow would drain all of Stannis' life powers. She said that it is strange that unworthy Thoros can resurrect[s03e07].
Thoros had no magical skills, he almost lost his faith in Westeros. His only magic skill was to drink as much as Robert Baratheon. He was flaming his sword using Wild Fire. But later he prayed for killed Beric, he suddenly was successful with resurrection. Giving the kiss of life was part of a funeral ceremony he gave Beric after his first death, and he was as surprised as anyone when it worked.[A Storm of Swords, Chapter 34,43, Arya VI,VIII]. He had no magic education - resurrection was a surprise for Thoros too.
Red priests are human beings, and like other human beings, they vary greatly.
So Spake Martin, R’HLLOR AND EVIL
They are trained at The Temple of the Lord of Light in Volantis to become red priests.
Many of the Old Blood of Volantis still keep the old gods of Valyria, but their faith is found primarily within the Black Walls. Without, the red god R'hllor is favored by many, especially among the slaves and freedmen of the city. The Temple of the Lord of Light in Volantis is said to be the greatest in all the world; in Remnants of the Dragonlords, Archmaester Gramyon claims that it is fully three times larger than the Great Sept of Baelor. All who serve within this mighty temple are slaves, bought as children and trained to become priests, temple prostitutes, or warriors; these wear the flames of their fiery god as tattoos upon their faces. Of the warriors, little enough is said, though they are called the Fiery Hand, and they never number more or less than one thousand members.
The World of Ice and Fire, The Free Cities: Volantis
A part of this training is to see the visions in the flames as Melisandre tells Davos so yesthey're trained to perform their magic.
"Fire is a living thing," the red woman told him, when he asked her to teach him how to see the future in the flames. "It is always moving, always changing . . . like a book whose letters dance and shift even as you try to read them. It takes years of training to see the shapes beyond the flames, and more years still to learn to tell the shapes of what will be from what may be or what was. Even then it comes hard, hard. You do not understand that, you men of the sunset lands." Davos asked her then how it was that Ser Axell had learned the trick of it so quickly, but to that she only smiled enigmatically and said, "Any cat may stare into a fire and see red mice at play."
A Storm of Swords, Davos VI