The Green Men are a group of "men" who formed an order to keep watch over the weirwoods on the Isle of Faces.
In the south the last weirwoods had been cut down or burned out a thousand years ago, except on the Isle of Faces where the green men kept their silent watch. Up here it was different. Here every castle had its godswood, and every godswood had its heart tree, and every heart tree its face.
A Game of Thrones, Catelyn I
"There they forged the Pact. The First Men were given the coastlands, the high plains and bright meadows, the mountains and bogs, but the deep woods were to remain forever the children's, and no more weirwoods were to be put to the axe anywhere in the realm. So the gods might bear witness to the signing, every tree on the island was given a face, and afterward, the sacred order of green men was formed to keep watch over the Isle of Faces.
A Game of Thrones, Bran VII
Although Maester Yandel is a bit skeptical in his writings in The World of Ice and Fire if the Green Men exist or not there have been a few tales of people going to meet them, the first is the Crannogmen and the second is of Ser Addam Velaryon.
"The lad knew the magics of the crannogs," she continued, "but he wanted more. Our people seldom travel far from home, you know. We're a small folk, and our ways seem queer to some, so the big people do not always treat us kindly. But this lad was bolder than most, and one day when he had grown to manhood he decided he would leave the crannogs and visit the Isle of Faces."
"No one visits the Isle of Faces," objected Bran. "That's where the green men live."
"It was the green men he meant to find. So he donned a shirt sewn with bronze scales, like mine, took up a leathern shield and a three-pronged spear, like mine, and paddled a little skin boat down the Green Fork."
"Did he meet the green men?"
"Yes," said Meera, "but that's another story, and not for me to tell. My prince asked for knights."
A Storm of Swords, Bran II
The dragon was Seasmoke, his rider Ser Addam Velaryon, determined to prove that not all bastards need be turncloaks. How better to do that than by retaking Tumbleton from the Two Betrayers, whose treason had stained him? Singers say Ser Addam had flown from King’s Landing to the Gods Eye, where he landed on the sacred Isle of Faces and took counsel with the Green Men. The scholar must confine himself to known fact, and what we know is that Ser Addam flew far and fast, descending on castles great and small whose lords were loyal to the queen, to piece together an army.
The Princess and the Queen
The following is also a tale of people trying to get to the Isle of Faces but never quite making it, though the ones that got close enough have said the Green Men are horned with green skin. Maester Yandel theorises that this is likely not true and just that the Green Men are wearing green clothes with horned headdresses.
Whether the green men still survive on their isle is not clear although there is the occasional account of some foolhardy young riverlord taking a boat to the isle and catching sight of them before winds rise up or a flock of ravens drives him away. The nursery tales claiming that they are horned and have dark, green skin is a corruption of the likely truth, which is that the green men wore green garments and horned headdresses.
The World of Ice and Fire, Ancient History: The Coming of First Men
It's worth pointing out that the stories/legends say that the Green Men had magical powers and that apparently they ride on elks. It's also been stated that they have antlers, similar to the quote above.
Bran shook his head. The day was growing old by then, and long shadows were creeping down the mountainsides to send black fingers through the pines. If the little crannogman could visit the Isle of Faces, maybe I could too. All the tales agreed that the green men had strange magic powers. Maybe they could help him walk again, even turn him into a knight. They turned the little crannogman into a knight, even if it was only for a day, he thought. A day would be enough.
A Storm of Swords, Bran II
"Coldhands," said Bran impatiently. "The green men ride on elks, Old Nan used to say. Sometimes they have antlers too."
A Storm of Swords, Bran IV