Byulnians were the inhabitants of Byulna, the native species of Lenny Kruger. The three "Common Men" he stole from the planet — Myamus, Jecomen and Kappaban — also belonged to the species. According to Lenny, even though they had access to time travel technology, they were not permitted to leave their own planet.
Byulnians were, as Rita noted, significantly larger than humans, though were capable of disguising themselves as members of the human race with skin suits. They drew power from attention and memories. Mark Carville, born Myamus as on Byulna, was able to draw strength, through photographs of past Common Men gigs, from the popularity of the Common Men across the world. As millions of people worldwide thought of him all the time, his strength grew stronger and stronger. According to the Fifth Doctor, this might be dangerous for him.
Because of their abilities, laws were put in place that prohibited the use of photographs and anything else capable of recording past moments. This was because the government was afraid that the population would grow power-hungry if given access to these powers. They also could not leave Byulna. Lenny, though, who opposed these laws, claimed that these were inherent traits of their species — their "true nature".
A strong thirst for domination caused Lenny Kruger to kidnap three children, and bring them to 20th century Earth to grow up as "human" in skin suits. The three, named Mark Carville, James O'Meara and Korky Goldsmith, eventually formed a soon-to-be-popular pop group, the Common Men.
This was what Lenny brought them to Earth for. He planned to harness the energy derived from the band's popularity, to become one of the most powerful men in Mutter's Spiral. In an alternate timeline, he succeeded in his plans and got away with it.
In the prime timeline, though, Lenny was caught by the Byulnians and brought to court for his crimes. As the government had no idea of Mark, James and Korky, the three were left on Earth, still thinking they were humans, and eventually maintained a spot as #2 in the British music charts. (AUDIO: 1963: Fanfare for the Common Men)