The algorithm tracks the number of free or unpaired neighbors for each triangle. We have 4 priority lists: the highest priority is for triangles that have at most one free neighbor, and the lowest is for triangles with all their neighbors still in the mesh. The algorithm now is simple: remove the triangle of the highest priority and pair it up with the highest priority neighbor. Then update the priorities of the remaining triangles.
The images enumerates the cases.
If we have a triangle that doesn't have a free neighbor, just pair it with a dummy neighbor.
If a triangle has only one neighbor, it is paired with that. This step may break the mesh apart, but doing so won't cause more unpaired triangles than postponing this choice.
If we have two neighboring boundary triangles, we pair them. In the left configuration this does not break the mesh, but in the right one it does. In that case we postpone that pair until any pair would break the mesh.
The last two cases are pretty straightforward and don't occur very often, and they cannot break the mesh. In fact, we can have the case 0 only right in the beginning when the mesh doesn't yet have a boundary.