There's a lot of precedent for the flayed man on as their sigil and there appear to be quite a few specific references of flaying happening in the books and before.
Reek, actually Ramsay Snow in disguise, suggests flaying people to Theon and actually flays the miller's boys before tarring their heads and putting them on spikes.
Reek stepped close. "Strip off their skins," he urged, his thick lips glistening. "Lord Bolton, he used to say a naked man has few secrets, but a flayed man's got none."
The flayed man was the sigil of House Bolton, Theon knew; ages past, certain of their lords had gone so far as to cloak themselves in the skins of dead enemies. A number of Starks had ended thus. Supposedly all that had stopped a thousand years ago, when the Boltons had bent their knees to Winterfell. Or so they say, but old ways die hard, as well I know.
A Clash of Kings, Theon IV
On their iron spikes atop the gatehouse, the heads waited.
Theon gazed at them silently while the wind tugged on his cloak with small ghostly hands. The miller's boys had been of an age with Bran and Rickon, alike in size and coloring, and once Reek had flayed the skin from their faces and dipped their heads in tar, it was easy to see familiar features in those misshapen lumps of rotting flesh. People were such fools. If we'd said they were rams' heads, they would have seen horns.
A Clash of Kings, Theon V
Note in the first quote Reek even alludes to Lord Bolton flaying people. Ramsay Snow, as himself this time, also flays Theon Greyjoy when captured at some point in time.
The maester touched his brow. "I am so very sorry, Jon. Your brothers died at the command of Theon Greyjoy, after he took Winterfell in his father's name. When your father's bannermen threatened to retake it, he put the castle to the torch."
"Your brothers were avenged," Grenn said. "Bolton's son killed all the ironmen, and it's said he's flaying Theon Greyjoy inch by inch for what he did."
"I'm sorry, Jon." Pyp squeezed his shoulder. "We are all."
A Storm of Swords, Jon VI
"The skin from the little finger of Theon Greyjoy's left hand. My son is cruel, I confess it. And yet . . . what is a little skin, against the lives of two young princes? You were their mother, my lady. May I offer you this . . . small token of revenge?"
Part of Catelyn wanted to clutch the grisly trophy to her heart, but she made herself resist. "Put it away. Please."
"Flaying Theon will not bring my brothers back," Robb said. "I want his head, not his skin."
A Storm of Swords - Catelyn VI
There are yet more quotes that allude to Lord Bolton flaying people as well as just his son.
"Lord Bolton is not in the habit of being questioned by servants." She crossed her arms.
The stableboy was still looking at the flayed man. He knew what it meant. "Three, you say?"
A Clash of Kings, Arya X
"Yes." Before you can learn to move you must learn to be still, Syrio Forel had taught her long ago at King's Landing, and she had. She had served as Roose Bolton's cupbearer at Harrenhal, and he would flay you if you spilled his wine.
A Feast for Crows, Arya II
Lastly, for some historical precedent to the sigil Jaime mentions the Bolton's flaying Starks,.
"Every great lord has unruly bannermen who envy him his place," he told her afterward. "My father had the Reynes and Tarbecks, the Tyrells have the Florents, Hoster Tully had Walder Frey. Only strength keeps such men in their place. The moment they smell weakness . . . during the Age of Heroes, the Boltons used to flay the Starks and wear their skins as cloaks." She looked so miserable that Jaime almost found himself wanting to comfort her.
A Storm of Swords, Jaime VII
The World of Ice and Fire gives us some more historical examples.
The enmity between the Starks and Boltons went back to the Long Night itself, it is claimed. The wars between these two ancient families were legion, and not all ended in victory for House Stark. King Royce Bolton, Second of His Name, is said to have taken and burned Winterfell itself; his namesake and descendant Royce IV (remembered by history as Royce Redarm, for his habit of plunging his arm into the bellies of captive foes to pull out their entrails with his bare hand) did the same three centuries later. Other Red Kings were reputed to wear cloaks made from the skins of Stark princes they had captured and flayed.
The World of Ice and Fire, The North: The Kings of Winter
The Rape of the Three Sisters is the name by which the Northern conquest of the islands is best known. The Chronicles of Longsister ascribe many horrors to that conquest: wild Northmen killing children to fill their cooking pots, soldiers drawing the entrails from living men to wind them about spits, the executions of three thousand warriors in a single day at the Headman's Mount, Belthasar Bolton's Pink Pavilion made from the flayed skins of a hundred Sistermen...
The World of Ice and Fire, The Vale