TL;DR: It is unclear for how long Shae and Tywin have been involved.
A good question and one which requires an in-depth analysis!
This issue has been discussed at length in a few locations:
It is hypothesised and re-butted that Tywin knew Shae all along and planted her with Tyrion. But let's do our own analysis here.
The Facts
Where did she come from?
What we know for sure, is that Shae was found in the tent of an unnamed "knight" and the details seem to be a little bit shady:
“Where did you find her?” Tyrion asked him as he pissed.
“I took her from a knight. The man was loath to give her up, but your name changed his thinking somewhat... that, and my dirk at his throat.”
...
Did you perchance note the name of this knight you took her from? I’d rather not have him beside me in the battle.”
Bronn rose, cat-quick and cat-graceful, turning his sword in his hand. “You’ll have me beside you in the battle, dwarf.”
-A Song of Ice and Fire: Book One - A Game of Thrones, Chapter Sixty-Three (Tyrion VIII).
It's definitely possible that Bronn just doesn't know who this knight actually is, or care.
Before all of this Tyrion mentions that he was given a 'body servant' by Tywin - there's no information on what a 'body servant' actually is or why Tywin has sent them for Tyrion. In the same paragraph, Tyrion meets and describes Shae:
Lord Tywin had sent him a groom and a body servant to see to his needs, and even insisted he take a squire. They were seated around the embers of a small cookfire. A girl was with them; slim, dark-haired, no more than eighteen by the look of her. Tyrion studied her face for a moment, before he spied fishbones in the ashes.
-A Song of Ice and Fire: Book One - A Game of Thrones, Chapter Sixty-Three (Tyrion VIII).
[emphases mine]
Tyrion then asks Shae herself about who she was with before him:
He asked her about the man Bronn had taken her from, and she named the minor retainer of an insignificant lordling. “You need not fear his like, m’lord,” the girl said, her fingers busy at his cock. “He is a small man.”
-A Song of Ice and Fire: Book One - A Game of Thrones, Chapter Sixty-Three (Tyrion VIII).
[emphases mine]
But if the person was so insignificant, then how and why was she with him? Bronn himself says that he had to fight for Shae because all the pretty ones were
taken:
“Splendid,” Tyrion said dryly, shaking off the last drops. “I seem to recall saying find me a whore, not make me an enemy.”
“The pretty ones were all claimed,” Bronn said. “I’ll be pleased to take her back if you’d prefer a toothless drab.”
Tyrion limped closer to where he sat. “My lord father would call that insolence, and send you to the mines for impertinence.”
“Good for me you’re not your father,” Bronn replied. “I saw one with boils all over her nose. Would you like her?”
-A Song of Ice and Fire: Book One - A Game of Thrones, Chapter Sixty-Three (Tyrion VIII).
[emphases mine]
Tywin knows all
Ok, it then becomes a little bit more suspicious when Tywin turns up knowing everything there is to know about Tyrion and Shae, even though Tyrion has done his best to keep her secret.
Tywin's Secrets
Lord Tywin himself is not without his secrets. It is also hypothesised that he frequented brothels himself. If you remember Varys showing Tyrion a secret passage from the Tower of The Hand to Chataya's brothel, he mentioned a 'previous Hand'; well, many people believe this to have been Tywin:
[Tyrion]“How is it a brothel happens to have a secret entrance?”
[Varys]“The tunnel was dug for another King’s Hand, whose honor would not allow him to enter such a house openly. Chataya has closely guarded the knowledge of its existence.”
-A Song of Ice and Fire: Book Two - A Storm of Swords, Chapter Sixteen (Tyrion III).
Many speculate that Tywin frequented brothels to fill the void of his loss of his wife Joanna. But he only ever did it secretly.
But what does G.R.R.M. say?
The author of the books, George R.R. Martin has been asked about this before, and he says:
I won't comment on the Tyrion / Tywin issue. Perhaps future volumes will throw more light on it.
-http://www.westeros.org/Citadel/SSM/Entry/2999
This most probably means that it is inconsequential to the story.
Conclusion
There's not enough conclusive evidence either way. I'm hoping that since in the TV-Show, they didn't include Tysha's story, that hopefully during Tyrion's time in Pentos and the rest of Essos that he will elaborate whether or not Shae was with Tywin from the beginning or just from after Tyrion's charges.
Tywin certainly didn't seem too fussed that Tyrion killed Shae, both in the show as well as in the books... After all she was only a whor... THRUM!
The crux of it seems to be that Shae saw an opportune moment to dump Tyrion and go straight for the source of the Lannister wealth!