I bought this the day I finished A Game of Thrones. It won the 1999 Locus award for best fantasy novel and the 2004 Ignotus award for best novel. In this book, two new narrating characters are introduced - Theon and Davos. And Theon's perspective is very interesting.
Just like A Game of Thrones, I highly recommend it. It is advertised as the height of modern fantasy, and that it certainly is. It is very long, but not boring. Instead of boring, it is engaging and has many cliffhangers that kept me reading long after I should have been asleep. I also recommend the TV series, it sticks surprisingly well to the original plot and the confusing parts are are a lot clearer in visual form.
(summaries of the narrating characters adventures)
Tyrion acts as the Hand to the King in place of his father. He continues his relationship with the whore Shae and does his best to improve the kingdom. He is badly injured in the battle between Stannis and Joffrey - of which Joffrey wins.
Catelyn helps Robb by negotiating with Walder Frey and betrothing Robb to one of Frey's daughters in exchange for passage. She also tries to negotiate with Renly and Stannis unsuccessfully. She is present when Renly is killed, and is rumoured to be his murderer. She learns that Winterfell is taken by Prince Theon Greyjoy and he has killed her sons Bran and Rickon.
Davos is sent by Stannis to take his ships and Stannis' men to King's Landing to fight in the battle against Joffrey.
Sansa is abused by Joffrey, but Ser Davos promises he will help her escape. The betrothal is broken when Joffrey agrees to marry Margaery Martell.
Arya is taken by Yoren and he says he will take her to Winterfell on his way to the Wall with the men. She pretends to be a boy. The group is caught and Yoren is killed and no one knows Arya's identity. She saves a man's life. Arya is kept as a slave, but the man she saved promises three lives in return. She gets him to kill tow and then save some prisoners. She is then taken as a cupbearer, but on learning she is getting a new master, she runs away with tow of the men intended for the Wall.
Bran remains a cripple and has to act as Lord of Winterfell in Robb's absence. Maester Luwin counsels him. When Winterfell is taken by Theon - Bran, Rickon, Meera, Jojen and Osha hide in the crypts.
Jon ventures outside the Wall with the Night's Watch. They hear more talk of whitewalkers. On watch they come across wildlings and kill them, but Jon allows his captive to yield. Later, the Night's Watch are left with no options but to flee and Jon (as commanded) yields to the wildlings while the rest of the Watch flees.
Theon goes back to the Iron Island only to find his father doesn't trust him and has appointed his sister as heir. Theon is given a small area to conquer, but instead he goes after Winterfell. He does not have enough men to hold it and struggles, and pretends to kill Bran and Rickon. He kills Ser Rodrik and others and manages to hold the castle.
Daenerys travels along desert with her khalasar. It is revealed that Ser Jorah has feelings for her. She gets to Qarth, and goes into a spirited house that gives her much to think about. They only want her dragons so she travels to the ports. There she finds that Magister Illyrio has sent ships to take her, her dragons and her khalasar back to him.