In mythology, Hermes, god of thieves, stole them when the young god was only a baby. Apollo soon found out who had stolen his cattle, as he was the god of prophecy, and took the sleeping Hermes to be judged by Zeus. While Hermes originally denied everything, he eventually had to tell the truth and confessed. Zeus didn't punish him however, as he found the story to be most entertaining and asked that he simply return the cattle. Hermes did and later invented the lyre, which he offered to Apollo as a present.
While trying to convince Percy to go on a quest, Hermes told Percy the tale of how he stole Apollo's cattle and the eventual creation of the lyre as an apology to Apollo.
They are kept at Triple G Ranch, a ranch were some believed to be extinct animals in Greek mythology are kept, because Apollo does not have the time to herd them. Before Percy accidentally went there, it was unknown to the god that the owner, Geryon, was breeding the cattle for meat. It was also said that they were being fed to the monsters of Kronos.
When Hermes told Percy and Annabeth that Cacus stole his caduceus. He said that Cacus once stole Apollo's cattle, but when Percy questioned Hermes that he thought he stole Apollo's cattle, Hermes said he stole it too but with more style.