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.