Besides the story of how he was castrated, we don't really get much backstory on Varys in the show. Below is his backstory from the books:
Years before Robert's Rebellion, Varys and Illyrio Mopatis (the merchant at the beginning of Season 1 who 'sells' Daenerys to Khal Drogo and gives her the dragon eggs) started a business in Pentos where Varys would steal items from lesser thieves, and Illyrio would sell them back to the original owners for a small fee. They soon became the go-to people in Pentos for retrieving stolen property, and they both got rich.
Eventually realizing that information is often more valuable than gold, Varys began building a network of spies. He purchased small, quick, and quiet orphan children, taught them to read and write, and set them to work copying the information in the letters, ledgers, and charts of the wealthy and powerful. (Varys' network of children spies eventually became known as his 'little birds.') Using this information to make insider trades, for blackmail, etc., Varys and Illyrio increased their wealth tenfold.
Varys eventually became so infamous that word of his abilities reached King Aerys II (the Mad King) in King's Landing. By this time the king was starting to devolve into paranoia, and he no longer trusted his wife Rhaella, his son Rhaegar, or his Hand Tywin Lannister. Aerys contacted Varys, who agreed to be the king's Master of Whisperers. Varys quickly gained his trust by pointing out traitors and schemers, and as the king's paranoia grew so too did Varys' influence.
At the end of Robert's Rebellion, Varys tried to warn King Aerys against letting Tywin Lannister's host through the gates. Grand Maester Pycelle convinced him otherwise, and King's Landing was sacked. Jaime Lannister killed the Mad King when he asked his pyromancers to burn the city to the ground, and Robert Baratheon took the throne for himself. Varys' talents were useful enough for him to be kept around, so he was allowed to remain Master of Whisperers.