It seems like in your image of the Teutonic Order you first have their military branch in mind, which they are arguably more famous for, however this was only one, comparatively short lived, aspect of its history.

In it's earliest beginning, the Teutonic Order was created not as a military order, like the Templars, but as a hospital like, well, the Hospitallers. However contrary to the Hospital of St. John in Jerusalem, from which the Hospitallers or later Knights of St. John emerged, which maybe even existed before the First Crusade, the creation of this German Hospital, or hospitale Alemanorum, as it was called at that time, was much more impovised. During the Siege of Arce in 1189, the pivotal battle of the Third Crusade, the Crusader Army besieged the port city of Acre, and, at the same time, was besieged and held in place by Saladins troops from the other side. Unter these conditions, with presumably many wounded and extremely bad sanitation, merchants from Lubeck and Bremen created a makeshift hospital unter the sail of one of their disassembled mercant cogs.

It is not clear at which exact point the members of the Teutonic Order took up arms in defence of the pilgrims to the Holy Land, like the Hospitallers and the Templars, however in 1198 the Teutonic Order was made a proper military order, adapting the Rule of the Templars for martial purposes and the Rule of the Hospitallers for charity and and their work at the hospitals.

So how does St. Mary fit in here? Before the loss of Jerusalem to Saladin in 1187 there was a hospital called German Hospital of St. Mary in Jerusalem (domus hospitalis S. Mariae Teutonicorum apud Jerusalem). It was founded by a wealthy German pilgrim between 1119 and 1129 in order to take care of his countrymen travelling to the Holy Land, and of course given up in 1187, when the city was taken by the Muslims. It is assumed, that there is some connection or at least tradition between this hospital of St. Mary in Jerusalem and the later Teutonic Order. However in later times in their own chronicles the Teutonic Knights stuck to the story of their foundation at Acre, not least because this earlier hospital was subjected to the Hospitaller Order, and the younger still emerging Teutonic Order wouldn't want to be swallowed by an older and larger military order, as was not uncommon during that time.

At the same time the veneration of Mary really kickstarted during that time, especially among the monastic order of the Cistercians who devoted all of their churches to the Virgin Mary. It was also a Cistercian, Bernard of Clairvaux, who wrote the first rule of the Templars, thereby creating the concept of a military order. Among the Templars, the Virgin Mary had a very special place in their liturgy, with the Marian Antiphone sung at the end of every canonical hour, a practice which the Teutonic Order adapted as well.(Thats probably why, when you enter "Salve Regina" into youtube, you'll get blasted with dozends of "Chant of the Templars" and the like, btw.) St. Mary had a close connetion to the concept of crusading in general, especially later in the baltics. The livonian bishop Alfred of Riga tried to establish that, as Jerusalem was the country of the son, Livonia was the country of the mother, "Terra Mariana," of course with the intention to attract more crusaders and get more papal support.

Lastly, I can understand how you came to feel about the Teutonic Order as "pretty nasty fellows", because apparently that's what appearing as the antagonist in the founding myth of at least three modern European nations does to your public image. However part of the idea of crusading is to carefully allign the concepts of violence and (just) war on one hand and pious Christianity on the other, and the institution of a military order came to be it's synthesis. As it turns out, despite having some critics of course, this symbiosis of militarism and monasticism that was the Teutonic Order was widely accepted, appreciated and supported to large extent among Catholics of that time. Apparently it was morally justifiable to wage ruthless and agressive warfare against an enemy even more ruthless, cruel and violent.