I know that in Medieval Latin i and j were interchangeable in sound.
Was the choice of the letter arbitrary, or were there rules dictating which letter to use depending on the situation?
I and J not only represented the same sound, I can't find evidence that they were ever considered separate letters in medieval times. Instead, it seems that during the medieval period, they were variant forms of the same letter (like Greek σ and ς, or β and ϐ).
As Hugh mentioned in the comments, the form <j> seems to have been used in the context <ij>, especially at the end of numerals. This use is mentioned in the Wikipedia article on J and in this guide to English handwriting 1500-1700 (although that source is about English, it makes several statements that may provide useful context about the development of I and J as distinct letters).
I haven't found any source that mentions any other special contexts that would condition the use of the form <j> in the medieval time period.
It was a difference between consonants (J) and vowels (I). Generally, use J when you were making a consonant version of the noise. Use I as a vowel version.
Rather than editing user637's answer, I decided to make my own. I'm sure you've died waiting, so here we go. With information from the comments and general knowledge which I possess, "I" was used in antiquity (until 1478) to represent both the consonant and the vowel. "J" just kind of popped out of nowhere in some Middle High German text to distinguish the two letters. To prevent simply restating someone's added information, read Jon's comment.
As for the preference of J, in modern Latin studies, it is usually replaced with the original I. However hard to find, there are little bits of information across the Internet (as far as Google will take you through results mostly about Latin America) available to confirm that until the nineteen-eighties or so, J was significantly more present in schools and printing. In some Latin terms being introduced to speakers of languages which never use I as a consonant, a J is often provided. If you want further information on the opinions of these letters, I suggest asking some of those who know more about this, such as the awesome people on this site. You can also search for yourself on Google. From what I've read, it appears as if "I" were more common in Medieval Latin. The reason I brought up modern sources is that, rarely, texts originally inscribed with one letter might be changed to the other in digital conversions and reprints. So, here's my answer, take it or leave it. I hope you could use something from this, but as far as my research-spree went, it's a mystery. Oh, and Latin texts by Old English speakers might be unclear in reading, as the English alphabet at the time was strictly for knowing how to pronounce their written language. This is why one word can have many spellings. What if the Modern English "spelling" could be "speling," "spehling," or anything else? For sounding out, a J or Y was certainly more common in such scripts.
So, hopefully, you survived that. To sum it all up, I don't really know, and you should listen to people who actually know about this. Were this somewhat helpful, well... okay, I'd do a few things: