In the very first episode of the first season, when Jon says goodbye to Bran, Catelyn stops him. Calls him by his name. He stops, and she says 'It should've been you'. Likely altered so people would sympathize more with Catelyn.
The character of Roz (the prostitute) does not exist in the books. At all. She's introduced in the show as a way to give Littlefinger more screen time.
Speaking of which, Littlefinger plays a very minor part in the first two books, it has been expanded significantly here. He's also 500% more smarmy onscreen for some reason.
Shae is much older and more worldly onscreen than in the books. She's also foreign in the show, and was not in the books. Book Shae is more bratty/youthful, and less sophisticated. Ironically, the character of Shae is becoming closer to the one in the book in season 2.
Littlefinger telling Sansa the story of how the Hound got burned. That's a big one. In the book, the Hound tells her. In a particularly menacing way, and threatens to kill her if she tells anyone. As Sandor/Sansa have a unique kind of relationship in the books, it was a bizarre re-write, and poorly acted by Gillen in the bargain.
Tyrion does not lecture Jon to be nicer at the wall. Tyrion, book Tyrion anyway, likely wouldn't have given a shit what Jon was up to. Jon was lectured by the armorer Donal Noye, who called him "A bully and a bastard". It was actually one of the strongest moments of the books and a good character building moment for Jon.
Tyrion did not get knocked out on the way to the battle against Robb's forces. He fought, and took a mild wound. I suspect this was changed for budget reasons. Not a big deal.
Catelyn's Uncle, Brynden Tully, is a fairly significant character through the first four books. He's been written out entirely. As too apparently have her father and brother, both of whom play not insignificant roles.
Meera and Jojen Reed play a very significant role in the 2nd book in Bran's storyline. They've been written out entirely.
Roose Bolton is supposed to be soft spoken to the point of whispering. In the show, he's been blustery. Odd change.
Margaery Tyrell is meant to be 16, but I like Natalie Dormer a lot so this is alright.
Stannis is never seen having sex with Melisandre, nor does she ever promise him a son. Stannis also has a daughter in the books, who seems to have been written out (and who plays a minor but not entirely insignificant role in a later plot line).
Davos has something like 7 sons. They've been condensed into one for show purposes.
Arya was not captured by Amory Lorch, nor did the Night's Watch fight a battle in the middle of a field. They defended the holdfast, and Arya, Hot Pie, Lommy and Gendry escaped, to be later captured by The Mountain and some of his men, including Polliver and The Tickler. Although Yoren does die in the books, he did not die a heroic death whilst cutting down a half dozen men.
Irri and Rakharo do not die in Dany's storyline. In fact Doreah is the only one who dies in the Red Wastes, and is presently the only one left alive in the show.
Robb does not ever meet a nurse named Talissa. This is either a new character, or (possibly) an alteration of a character who does not appear until the third book. Depending on how this plays out it could have MAJOR effects on later events.
Vargo Hoat and the Brave Companions have either been written out of the show, or are not going to appear until the third season. They played a small role in book 2.
Tywin Lannister never met Arya at Harrenhall, and Arya was never his cupbearer. She was a serving girl under a cruel man named Wease. Wease was one of the two kills Jacquen H'ghar performed for her. The other one was one of the Mountain's Men, whose name escapes me. It was not Amory Lorch. Nor was one of her kills The Tickler, whose death in season 2 now alters a significant scene in season 3.
Jorah Mormont never gives Dany an impassioned speech about sailing to Westeros and making the people rise up for her. Quite the opposite actually, he's quite ruthlessly pragmatic in the books. She doesn't marry Xaros because as per Quarthian marriage custom, she would have owed him a gift of his choice that she could not refuse, and he would have chosen a dragon.
Dany's dragons are never kidnapped, and her Khalasar never murdered. That's entirely new.
Ygritte does not escape. Jon lets her go. Significant character building moment for Jon. He also does not run off after/with her.
Jon never sees Craster giving up a son to The Others (called The White Walkers in the show), and is never knocked out by Craster, and never catches shit about it from the old bear.
Qhorin Halfhand requests Jon Snow come with him on the ranging. Jon doesn't ask to go.
Bran never stands up to Theon when Theon seizes the castle. He's confused and scared. Theon also doesn't do it in the middle of the fucking day, they scale the walls at night.
There's never any confusion about whether it might be the Lannisters attacking Torrhen's Square. It's known all along that it's Iron Men. Weird, pointless change.
Ser Rodrik Cassel was not killed by Theon at Winterfell. He wasn't even at Winterfell. He was at Torrhen's Square.
The Iron Men in general are much changed. In the books they are puissant warriors, very similar to Scandinavian Vikings in manner and appearance. In the show they look like dirty, ragged bandits.
When Rodrik Cassel is killed in the show, Dagmar (who was also at Torrhen's Square in the book) says he needs to "pay the iron price". Paying the iron price means killing a man to take what he owns instead of buying it with gold. Weird misappropriation.
Renly is not stabbed by the Shadow, it slits his throat (through his armor, no less). Catelyn and Brienne are the only ones who see it happen, and Brienne is suspected for a long time. Loras, for instance, believes its her for quite a while.
A not insignificant subplot involving a 2nd shadow, the castle of Storm's End, and a bastard son of Robert's has all been cut.
Tyrion's character in general is much changed. He's still witty and affable in the books, and very smart, but he's bordering on a Mary Sue in the show. A lot of his less genial moments have been cut or slightly altered to make him more sympathetic. For instance, he threatens to have Tommen raped and beaten if Cersei harms a prostitute.
Shae does work as Sansa's handmaid for a time, but Sansa never trusted or liked her on any level.
The wolves are under-represented in the show, but that's alright. CGI is expensive.
The entire Riverlands have been cut along with the Tullys, more or less. They were part of Robb's host, and also part of Robb's kingdom. King of the North and the Riverlands. So basically one of the 7 kingdoms has just curiously been omitted entirely. Perhaps we will see the Tully's and the Riverlands in season 3. I'm not holding my breath.
Numerous smaller characters and subplots have been changed or abandoned. Same with lines of dialogue, some made worse. Tons of needless whorehouse scenes have been added in their place.
Joffrey's cruelty and stupidity have been dialed up to 11 in the show. He was always cruel and stupid but it's at ludicrous levels in the show. The beating/abuse of the prostitutes, for example, never happened. Still, Joffrey is a monstrous prick either way, so it's hard to get too ruffled about that.
You'll be introduced to Ramsey Snow, possibly this season. He's meant to already be in Winterfell, under a different name. This has MAJOR implications for events in this book, and future books. No idea why they've gone about it this way.
Asha (Yara) is a lot more charming and a lot less brittle in the books. No idea why they've written her the way they have for the show. Balon is pretty on the nose though.
Numerous significant Ironmen characters are missing. They go on to play moderate to major roles later on. As the Ironmen sections in the books have often been decried as examples of Martin over-indulging in side plots, this may be an area where HBO decided to do judicious pruning.
Bronn was never made captain of the guard. Given Bronn's general personality, the very idea of it is somewhat ludicrous. That position went to Ser Jaclyn Bywater. Done to condense the number of character on screen, no doubt.
Sansa was not almost raped in the riot. A secondary character who featured prominently in several books was. She was almost dragged off her horse though. And while Tyrion's chastisement of Joffrey was entertaining, it was altered from the book, which did the same scene better and with the same amount of dialogue.
The Pyromancers were never making Wildfire for Cersei. Tyrion just stumbles across the fact there's thousands of jars of it festering under the city and decides to try and make use of it.
A fairly significant subplot involving a giant chain that Tyrion has made is either cut or not yet started.
Stannis is actually being reasonably well portrayed, but is positively starved for screen time. We've also not heard anything about his goofy magic sword, which gets prominent mention at numerous junctures.
The scene with Melisandre and the poison was poorly framed. She drank first, and the guy wasn't half dead already by the time she took her drink. Was a weird way to shoot that.