Sansa is frequently described as a "little bird," because she's kept in a gilded cage, always says sweet things and repeats back whatever is expected of her. She's taken under the wing of Petyr Baelish, masquerading as his natural daughter. Baelish changed his sigil to a mockingbird, which also repeats noises made by others.
There's some definitely Stealth Pun humor with the Kettleblack brothers. Their accusing others of their own crimes fits with the proverb about what the pot called the kettle.
There's likely a heraldry Stealth Pun in Stannis' coat of arms that has a the Baratheon stag enclosed in a flaming heart. A hart is another word for a stag.
The sigil of house Baratheon is a stag—the term "horns", refering to being cuckolded, is derived from the stag's custom of giving up its mate after losing a fight. House Baratheon is plagued by all kinds of adultery. Robert is cuckolded by Cersei, Stannis makes shadow babies with Melisandre, and Margaery Tyrell is only "officially" a virgin on marrying Renly.
In A Storm of Swords, Tyrion thinks: "There was this to say about weddings over battles: it was less likely that someone would try to cut off your nose." As two particular weddings in that book proved, weddings are worse than battles sometimes.
In A Game of Thrones, Arya jokes about her hypothetical coat-of-arms, wondering if it would be a wolf with a fish in its mouth. Later on Arya, warged into Nymeria, pulls Catelyn's corpse out of the river.
Theon is described joking about Hodor that whatever else you could say about his intelligence, he definitely knows his own name, though he apparently forgot that "Hodor" isn't Hodor's name. Theon then becomes so tortured that he's been conditioned to forget his own name.
Maps of the world◊ show that many coastlings and the land across from them fit together, such as the Sea of Dorne and that headland in the Disputed Lands, or Shipbreaker Bay and that headland north of the Sea of Myrth, or the Sea of Myrth itself and the headland Rain House is on. This is in accordance with real-world plate tectonics, such as how South American and Africa fit together.
Combined with Fridge Horror. In a lot of aspects, Theon is shown to be a foil to Jon Snow. Because of this, its interesting to note that while Jon performing oral sex on Ygritte is one of the most romantic scenes in the story, Ramsay forcing Theon to perform oral sex on Jeyne Poole is one of the most horrific.
Jalabhar Xho is an analogue to Viserys, another exiled "beggar king." Just like Viserys, he is powerless to do anything but beg those more powerful to return him to his throne. Jalabhar, however, is apparently more content to wait.
Ned is surprised to see a direwolf south of the Wall. With the Others rising, it's an early indication that the land north of the Wall is becoming uninhabitable. Mance Rayder and the wildlings eventually reveal a similar intention to flee south.
Dorne was the one Kingdom to resist the Targaryen invasion enough to manage to bargain with them and capitulated only with marriage and cultural concessions. You could easily put this down to the number of mountains and sheer expanse of baking hot sand alone. Until you remember that the people using these environments to resist being taken over had been settled by refugees from Essos — fleeing extermination by Valyrian lords. They had had plenty of time to work out what to do against dragons (and, most importantly, what not to do) what with the tales of the rout.
Dany "pointedly" asks Missandei whether Unsullied could be used against her if she decides to resell them. Later it becomes clear that Dany had no intention of selling slaves. She was trying to discover if the Unsullied could be turned against Astapor's Good Masters.
One of those most minor cases but still pretty funny is Sam Tarly unwittingly smashing Melisandre's justifications to pieces. During A Clash of Kings, Melisandre tries to justify her morality to Davos by claiming "when half an onion is black with rot, it is a bad onion." Much later, when the Night's Watch survivors have dragged themselves back to Craster's Keep and are being fed, one of Craster's wives gives out some onions, and Sam receives one that is half black with rot. He simply cuts it in half, tosses the rotten portion away, and eats the good half.
At the Red Wedding, the musicians are described as terrible, then revealed shortly thereafter to be crossbowmen, explaining why their musical talents are lacking.
A lion is also known as "King of the Jungle" and a stag as "King of the Forest". The Lannisters undermined the Baratheons for quite some time, which escalated into a clash of kings.
The Baratheons are known for their stubbornness, which is reflected in their sigil the stag. Two Baratheon bastards, Gendry and Mya Stone, are likened to a bull and a mule respectively, which are animals known for their stubbornness, thus hinting at their parentage without being actual stags.
The Ironborn worship the Drowned God, whose eternal enemy is the Storm God. The Iron Islands first fought against the Stormlands for dominion over the Riverlands and the Greyjoys later get crushed by Robert/Stannis Baratheon, who are Stormlords. Currently Aeron, a zealot, is increasingly preaching about the struggle between the two gods and it turns out that a Baratheon is coming for the Ironborn yet again and pushing them back. Both Victarion and Stannis are the younger brothers in charge of two of the biggest fleets in Westeros, are in the shadow of their older brothers, known for their lack of sense of humor, were in direct conflict with each other and ultimately ended up turning to the Red God.
Dany's surreal vision of a wolf-headed king reigning over a feast of dead men. It's not even as metaphorical as it first seems.
Patchface's song: "Fool’s blood, king’s blood, blood on the maiden’s thigh, but chains for the guests and chains for the bridegroom, aye aye aye."
Theon's nightmare after conquering Winterfell. In his dream Theon is sitting by a table that is surrounded by people who are dead. Theon wakes up when Robb Stark and Greywind enter the room covered with savage wounds. Theon sitting by the table foreshadows Theon's fate. In book five, Theon often reminds himself that Theon Greyjoy died in Winterfell and that only "Reek" remains.
And the Ghost of High Heart: “I dreamt a wolf howling in the rain, but no one heard his grief. I dreamt such a clangor I thought my head might burst, drums and horns and pipes and screams, but the saddest sound was the little bells."
Sandor promises to take Arya to her uncle's "bloody wedding," which turns out to be prophetic.
Petyr claims that he's slept with Catelyn, but we later learn that it was actually Lysa who slept with Petyr after a feast while he was passed-out drunk, and he thought at the time that she was Catelyn. (He later knowingly sleeps with Lysa after the duel, when he's not in the best state of mind either.) The fact that he's been making this claim for years afterwards shows how psychologically damaged he is over Catelyn.
Shae recognizes a disguised Varys because she says a whore has to learn to see the man, not his appearance, or she ends up dead. This is ironic given that she vastly misreads Tyrion when he confronts her after her betrayal, causing her death.
Oberyn says that he'd sooner die with a breast in his hand than a weapon. He dies in battle soon afterwards.
In A Clash of Kings, Bran, Rickon, and their Frey wards are playing a game in Winterfell called "The Lord of the Crossing", which they learned at the Twins. One player is the Lord of the Crossing, who stands in the middle of a bridge with a staff. The player who wants to cross must swear oaths to the crossing, which they must keep unless they say 'mayhaps' without the Lord noticing. In A Storm of Swords, Walder Frey, the real Lord of the Crossing, swears oaths to the Starks immediately prior to the Red Wedding, but sneaks the word 'mayhaps' into his phrasing. He even reminds them that he's given them leave to make the crossing at the Twins on many occasions, "and you never said 'mayhaps'" — which, according to the rules of the game, is an immediate disqualification for anyone who manages to disarm the Lord and cross the bridge.
Ned mentions Barra, one of Robert's bastards, in front of Robert and Cersei. In the next book, we learn Cersei has had her killed. She might not have even known about Barra if Ned hadn't mentioned it.
It is heavily implied that Theon has been gelded by Ramsay. Then there is the line: "Lord Ramsay never took anything but skin unless you begged for it."
On the suggestion of 'Reek' Theon has a pair of miller's children killed so he can pass the bodies off as belonging to Rickon and Bran. Theon reflects that he slept with the miller's wife a few times. Given that one of the boys is young enough to pass for Rickon, Theon may well be guilty of Offing the Offspring on top of everything else.
Littlefinger tells Ned that Starks melt when they come below the neck. This makes sense with the whole "Starks as ice" thing they've got going, but also remember that Ned's father was burned alive when he went to King's Landing.
There are numerous references to weirwood groves being cut down and burned when people change faith. It doesn't look like a big deal (just some religious warfare), right? Then we learn, when Bran is being trained by the One-Eyed Crow, that weirwood groves contain the minds of all the greenseers, and record all the history they've ever witnessed. In other words, burning a weirwood grove is like burning a thousand-year-old library composed of sentient beings.
The parallel between the Baratheon brothers' health after they become king. Both Robert's and Stannis's health declined drastically once they donned a crown and people are remarking that they have become shadows of their former selves. Both went down a slow self-destructive path with a lot of self-loathing, which is especially hard to swallow for them since, like most members of their house, they were born with great physical prowess and as gifted warriors. Ironically, Renly, who was in his physical peak, was enjoying life in general and didn't care as much for fighting, got a quick death once he became king in his own right.