A Turing machine has a simple loop of reading the current tape cell, and depending on the current value, writing a new value, changing state and moving the read head on the tape. The paper shows that there are cards in MTG which can be used to implement that kind of loop.

The tape is represented by tokens whose strength increases with their distance from the read head, such that the current cell is the weakest one. On every loop iteration, it gets killed (read) and triggers different effects depending on its type, such as getting replaced (writing a new value), changing the effects that will be active on the next iteration (changing state) and dealing damage to one side of the tape but not the other (moving the read head).

Magic is played by taking a card from the top of your pile and following the instructions on it, then your opponent does the same. In normal games the decks are shuffled, but for this to work you have to be able to program the order of the cards in both decks. In this paper they program the game by constructing the decks using a subset of cards that all have mandatory effects.

I think what they do is set up a sequence of cards that 'initialises' the game state with various creatures and resources. These together with the game rules form the Turing machine. Then they have a sequence of cards that correspond to the 'paper tape' of symbols a Turing machine operates on.