Gendry came to work for Tobho Mott when an unnamed "Lord" paid for his apprenticeship.
"The truth now," Ned urged. "The streets are full of strong boys. The day you take on an apprentice without a fee will be the day the Wall comes down. Who paid for him?"
"A lord," the master said reluctantly. "He gave no name, and wore no sigil on his coat. He paid in gold, twice the customary sum, and said he was paying once for the boy, and once for my silence."
"He was stout, round of shoulder, not so tall as you. Brown beard, but there was a bit of red in it, I'll swear. He wore a rich cloak, that I do remember, heavy purple velvet worked with silver threads, but the hood shadowed his face and I never did see him clear." He hesitated a moment. "My lord, I want no trouble."
A Game of Thrones, Eddard VI
While it is not 100% confirmed (to my knowledge), there is a very strong indicator that Varys has been keeping an eye on Gendry, and acting in the interests to keep him safe. This would seem to suggest that Varys either himself in disguise, or through the use of another person who may have been a Lord, secured Gendry's apprenticeship.
This quote is after Tyrion exiling Janos Slynt, who had been ordered to go around and kill all the Bastards. We know that the Gold Cloaks are still looking for Gendry after he leaves King's Landing (Yoren's crew), and he is the only other known bastard from King's Landing identified in the story who matches that description from Varys.
"Not enough to save this child, it would seem"
"Alas, no. There was another bastard, a boy, older. I took steps to seem him removed from harm's way ... but I confess, I never dreamed the babe would be at risk. A baseborn girl, less than a year old, with a whore for a mother. What threat could she pose?"
"She was Robert's," Tyrion said bitterly. "That was enough for Cersei, it would seem."
A Clash of Kings, Tyrion II
Typically with Lords, the identifying mark is a sigil or the colour scheme of their dress, but it's of note that there is no specific sigil mentioned in that description. The colour might match a House whose colours are purple on white, e.g. House Dayne (http://awoiaf.westeros.org/index.php/House_Dayne), but there is no confirmation, so it's hard to speculate who or why.