The Megara were microcellular metallic biomachines. They could fly through the air. They communicated with each other using a special language. The Megara believed that "humanoids" were inferior because they were not totally capable of knowing the truth.
At one point, a galactic federation appointed them to uphold the law. The Megara found the federation in contempt of court and destroyed the galaxy. They were sometimes assigned to transport prisoners. When two of them transported Cessair and her servants, she escaped and they pursued her to Earth.
When Romana was kidnapped by Cessair and taken captive aboard her ship, the Megara were alerted to her presence after the Fourth Doctor went to rescue Romana. They put the Doctor on trial and sentenced him to execution. Through the trial the Doctor was able to get the Megara to recognise Cessair, and they turned her to stone. (TV: The Stones of Blood)