It is heavily foreshadowed... but I think Martin masterfully wrote it in a way where the audience reading it gets into a complete shroud of denial until it actually happens. I think why it remains so effective is that so much crap happens to the Starks, that despite the rug being pulled out from under you multiple times in the previous books (Ned, Winterfell razed, and basically every Stark thinking every other Stark is dead) you see Robb amassing his armies, Arya heading to the Twins to meet her brother and mother, and a compromise made with the Frey's with the next step to take the battle to King's Landing and you can't help but fall into thinking that this could be traditional narrative where there's a happy reunion, and the Starks are redeemed. The Red Wedding literally is a complete severance of Robb's arc as a hero, which despite being in Martin's world for some 2000 pages by that point, you can't help rooting for. It's like if Luke and Leia were brutally betrayed and murdered in ROTJ during the planning of the attack of Endor.
This being said, Martin was VERY VERY careful to make sure that the audience always had some degree of distance from Robb. He was never a POV, nor did we have a POV that was directly with him during most of his exploits in ACOK, and only heard about him from hearsay that the POV characters heard.
I mentioned before a long time ago that I was curious though how the show would address this. It looks like they expanded his role, so I wonder how this will change the impact of the Red Wedding. With an expanded role, he'll no longer be a distanced character but right up front and center, perhaps even becoming the defacto "protagonist" that the audience wants to win. I do agree with PhoenixDark that this'll make the event even more tragic in the show.
I also just have to say that I still think it's the height of stupidity to end a season (like S3:Ep 10) DIRECTLY on the Red Wedding, mainly for the reasons above. With Ned, it was different; he tried, he failed, he died, end of character. He really had nowhere else to go. As I was saying above with Robb, it's a totally different story where an expanded role will mean his hero arc is disrupted, and as huge of a troll that it would be, I can see basically a lot of the TV only audience saying "fuck this show" and MEAN IT this time, and not watch it when it comes back 8 months later since they've already written it off. I think you need to give the audience some levity.
I say, S3: Ep 9: the red wedding (title of the episode "The Rains of Castamere", calling it now.
) and S3: Ep 10 ends with Joffrey's death, but leave it at that. S4 could open with Sansa escaping, etc and move some of the BIG Wall stuff to S4, plus the resolution of the rest of ASOS (which there is a lot, Red Viper, Tyrion escaping, finish up with Brienne/Jamie, Arya/Hound/Tickler stuff) and maybe start addressing some of the AFFC/ADWD stuff at that point, and I think it'll fill out nicely.
So anyways getting back to the original point, I think that Robb's death IS telegraphed early on... but that still doesn't take away the impact.