Complex sentence: Upon their return from exile they entered Muiredach's service and were eventually told that they could have their own territory, sending them to make "swordland" of "Ulaidh" (Ulster).
Split into simpler sentences: Upon their return from exile they entered Muiredach's service and were eventually told that they could have their own territory. Hence they where sent to make "swordland" of "Ulaidh" (Ulster).