How does Advent mark Supply Crates for extraction?

There doesn't need to be an ADVENT soldier near the crate for it to be marked.

I'm not sure about the actual algorithm - they appear to get marked starting with the closest few (to your starting area, I assume) as soon as you are discovered.

It seems to be random, as loading a quicksave and ending the turn usually makes Advent chose a different pair of boxes.

That said, I would recommend taking a Reaper on the mission and silently sniping most enemies.

If you are lucky and clean up the map of all enemies (lost included) before the next lost wave spawns you end up winning the mission and getting all the crates.

In order for XCOM to mark a crate, they need a soldier adjacent to it (and marking a crate breaks concealment!). Is the same true for advent?

No. I've seen crates being marked that had no pods around them (as I had already cleared the area).

Thematically, it seems that ADVENT already know where their crates are, and they simply pick them up when they want to. I would assume that "marking" the crate means indicating that it will be picked up, so any ADVENT personnel can clear the area, and possibly for the crate to "light up" so that the crane operator has a visual confirmation.

XCOM, however, needs to attach that balloon to the crates, which requires them to physically approach the crate and attach the balloon.

Marked Crates are visible through the fog of war - if I see a crate get marked, does that mean an Advent patrol is nearby?

Going by the previous answer, I would say no. From experience, ADVENT seems to target crates that are closest to my XCOM soldiers.

SkyHiRider is somewhat correct when he said that it's random. I've also noticed that reloading a save file might cause ADVENT to select different crates. However, it is not fully random, as the selected crates were all very close to my XCOM soldiers.
There is some randomness going on, but it does heavily favor crates based on distance to XCOM soldiers.

So what you might conclude when a crate is marked through the fog of war, is that this crate is probably one of the crates closest to your soldiers. But I'm not sure how much of a guarantee that is. ADVENT has consistently marked the crates closest to me in all my missions so far, but I've only done 4-5 of those crate missions.