Cersei could have found out about Shae from the other handmaid she threatened in the last episode (from Sansa's flowering scene). I think it was a pretty stupid move on Shae's part, seeing as she doesn't have any "little birds" or any spies of her own to uphold the threat. It would be easy for the maid to run and tell Cersei, Shae really can't do anything to stop her, so all she's done is just cast suspicion on herself.
Still, I think it's a possibility that the added character 'Ros' will take Alayaya's place though.
What I'm personally most concerned about at the moment is Jon's storyline. I think it's crucial that he join the wildings on Qhorin's orders. If he forsakes any vows without being commanded to, it would severely change the character, IMO. So I am a bit worried, but I'm assuming (hoping) that Jon is rescued by Ghost and/or Qhorin and the other black brothers in this episode or next, giving the story a chance to play out as it did in the book. This way the small divergence would only help make it a more reasonable choice for Qhorin to choose Jon to join them, I suppose, by making it look more likely, from the wilding perspective, that Jon would betray the NW.