I had one brief conversation with a red coat friend in a hub. She said GCAs (Gate Concierge Agents) are assigned to a gate using the automatic scheduling system that hubs already use for telling a GA which flight to work; no one at the airport really knows how a certain flight is picked for Early Valet... they just pull up the schedule and it tells them where to go.

I didn't ask how they identify medallions. If it were my job, I would look for brag tags, or bags that look like they've been checked a lot (a million pink tag stubs, bag tag stickers, international tags, etc.). If I were at the gate and a medallion came up asking about an upgrade, I'd offer it then too.