I can guess the 'why' was simple Roman snobishness. Rome was civilization after all, and its people wouldn't dare sully their tongues with foul foreign words. Why, they were really doing the poor savages a favor!

I'm afraid you're very off the mark here. Why does English Anglicize foreign names and words? Why does French? Or German? Or Japanese? Or literally every other language on the planet? To make them easier to pronounce, more natural to read, and to allow them to fit into that language's morphological rule structures. This is particularly true in inflected languages like Latin or Greek, where inflectional endings that might not exist in foreign languages (such as Semitic languages) but which must be present in inflected morphology must somehow be constructed to allow foreign words to be used within Latin syntax. There's no snobbishness in the Anglicization of French or German words in English, it's purely because those are two different languages and they have different phonologies--perfectly recreating a foreign language's phonology in your own is patently impossible. There's no such thing as a direct representation of a foreign word by any language, it's always a phonological approximation using the phonology available within the language that is adapting the word, as well as any considerations of morphology (like the way that we add "s" in English, an inflectional ending, even to Japanese words which not only do not represent plurals like that, but do not represent plurals at all).

Further, I would argue that this idea of Roman "snobbishness" that seems to be very common on the internet is very very uninformed, an inability among certain circles to separate the phenomena of modern colonialism with the ancient world, which are vastly different in just about every way (in particular the bit about "doing the poor savages a favor" leads me to believe that you have fallen into the trap of the influence of this school of uninformed thought--such an attitude is simply not present in antiquity). In general this isn't really very relevant to our present discussion, but I'll at least comment on the use of foreign terms in connection with your assertion that Romans would not "sully their tongues" with "foul" loan words. A large part of Latin vocabulary is composed of load words. The Romans adopted Greek vocabulary in bulk (and although the Romans did not consider the Greeks on the same level as, say, the Scythians, they most certainly were not the equals of Romans), the majority of Latin's words for vehicles and wheeled transport are Gallic words adopted straight into Latin, and a huge number of extremely old words in Latin derive from Sabine or Etruscan words. The Romans had little problem with adopting foreign words.

Since Latin's phonology is constrained by its rules and Latin's morphology demands that inflectional endings be present within word structures it becomes necessary to adapt foreign words into the Latin language. So, this begins our answering of your real question:

But how did they go about doing it? Was there a formal system for converting sounds or did they just make it up on the spot, going with whatever they felt sounded sufficiently Roman?

The answer is that it very much varies on a case-to-case basis, and it wasn't always standardized or even agreed upon how to render foreign words into Latin. With some languages the Romans lucked out. Most forms of Gallic, for example, were rather closely related to Latin and Italic languages, and were phonologically and morphologically similar enough that only minor changes were needed. Some Gallic words could be adopted without any changes at all, such as raeda or carrus, and many personal and tribal names could be rendered straight into Latin without any changes. Gallic appears to have mainly differed from Latin in terms of its consonantal structure (Gallic had a lot of strange consonant clusters that Latin tended to avoid) but vocalically it seems to have been extremely close, especially to Archaic Latin. Greek also was close enough to be rendered easily with the addition of letter's like Z that the Romans did not use with their own words. However, Greek presents two problems that Gallic does not. First, Greek has an accent type very different from Latin's, a pitch accent as opposed to a stress accent. Latin could not reproduce this easily, and so in Latin discourse Greek loan words usually lost their pitch accents, unless you were quoting an author verbatim or something. Second, Greek had a much more complicated inflectional structure than Latin, at least Classical Latin. Gallic's morphology was very similar to Latin's, but while Greek's could be sometimes other times it was very different. The usual standard for converting Greek nouns into Latin was to convert Greek nouns into Latin declensions and use the standard Latin declensional endings, even when they were not correct to the Greek. In literature you sometimes find people like Virgil just writing out the Greek case endings in Latin letters, but this is rare and very literary.

What about other Indo-European languages? Recall that Indo-European languages, particularly those nearby Italy and therefore related to the Italic languages more closely, shared origins, and thereby had very similar syntax, phonology, and morphology. It was quite an easy matter in most cases to adapt other Indo-Europeans of closely related families into Latin phonology and morphology. Germanic words gave the Romans a tiny bit of trouble, mostly because they had lots of sounds that Latin simply couldn't mirror, but since Germanic morphology and declensions were fairly similar to Latin they didn't at least have to adapt those that much. So "Arminius" is probably a pretty close rendition of the form the name originally took, although there was probably an initial aspirate that disappeared in the Latin form of the name (Germanic words tended to have lots of aspirates that Latin couldn't replicate). The case ending is probably pretty close. "Hermann" is simply the modern name that probably evolved from the original name of the chieftain whose name was rendered into Latin as "Arminius."