The Teuthoidians were slug-like creatures from the beginning of time, one of the first space-faring races in the universe.
Technology
Their spaceships were covered in 'coloidal secretions' which helped them around their own ship, but slowed them down on other ships, eg The Eschaton. (BFA: The Key 2 Time - The Chaos Pool)
History
When searching for the Chaos Pool, they encountered the Eschaton, a ship from the planet Atrios, captained by Captain Pargrave under the watchful eye of Astra of Atrios. When their ship was destroyed, the Fifth Doctor thought to return them to the other end of time, where they belonged. However they were seen to attack him and Zara before they reached the Chaos Pool. During the battle between Chaos and Order, they sided with the White Guardian in the search for the Doctor, Zara, Amy and Romana through the fourth segment of the Key to Time. They switched sides ib the castle Safe Place, before Romana was converted into the sixth segment (even though in fact Astra had decided to retake the segment and be converted herself) after they had escaped the castle using Zara's time ring. The Castle was also converted back into a segment with Freedom's, Freedom fight and the Teuthoidians trapped inside. When the key was destroyed all inside the Key were returned to their respective times. (BFA: The Key 2 Time - The Chaos Pool)