[CAUTION, HERE BE SPOILERS]
How is this new story connected with Half-Life 2?
Half-Life: Alyx takes place after Half-Life and 5 years before Half-Life 2. In the game, we learn about G-Man's imprisonment, possibly explaining Freeman's extended 'leave' of the almost 20 years that bridge that gap. It refers to the planned-but-never-released Episode 3, offering an alternate timeline to the Episode 2 climax.
How can Alyx find Gordon Freeman after he arrives to City 17?
In Half-Life 2, Alyx finds Gordon by accident. That is, to their surprise, as it certainly must have been the G-Man who orchestrated it this way: after all, Barney Calhoun is at that very moment working undercover as a Civil Protection agent at the City 17 Trainstation, and able to help the mute physicist to elude the Combine. After Barney's conversation with Dr. Isaac Kleiner, Alyx must have picked up on the fact that the legendary Gordon Freeman has finally arrived, and decided to go meet him.
Initially, her enthusiasm could be explained by Gordon's status, but now, in the light of this new Half-Life instalment, it could mean the G-Man was behind this encounter all the time.
Why does Alyx not remember what happened during the prequel and joins Gordon on his journey?
Since at the moment no canonical information is available on this matter, we can only speculate. There are multiple potential explanations for this, and I think the one that is most reasonable, ultimately, is the one that permits Valve the highest level of creative freedom1:
Temporal explanations:
Alyx has been instructed by the G-Man to keep quiet about their encounter and agreement.
Her being in the G-Man's employ sheds an entirely new light on the collaboration with "the Free Man" during Half-Life 2 and the additional episodes. Perhaps Alyx was given clear instructions by the G-Man to remain silent, possibly not to influence the regular flow of time, maybe even in order to retain the situation in which her father is saved, or to protect Gordon or mankind.
Although this would cast a shadow on the relationship she builds up with Gordon, it would allow for a more psychological kind of gameplay - ideal for exploring VR possibilities.
Alyx (at that point) has no memory of the encounter.
Similar to what human Combine volunteers have to go through to climb the ranks, Memory Replacement might have been used to shape Alyx into a more effective agent, or make her forget her alliance. Alternatively, an Advisor would potentially be able to induce localized amnesia, and the G-Man himself might have powers beyond those we are familiar with.
Extratemporal explanations.
These are more likely, since Valve seem eager to start experimenting more with space-time manipulation, especially since it has been prevalent in their franchise since the beginning2:
The agreement with Alyx has caused a diverging timeline.
As the G-Man, at this point on the timeline, intervenes with a future event, the timeline necessarily has to split here. This would imply that Half-Life 2 took place in an alternate reality.
The events take place on a different timeline altogether.
The G-Man might have shown her an emotionally poignant moment from an alternate timeline in which her father dies to gain her loyalty. Eli Vance's death in that case never really occurs. After all, if he saved Alyx from the Black Mesa Incident, why would he still feel the necessity of rewarding her, unless it is for personal interests?
There is also an out-of-universe reason to be found:
Valve has stated they weren't happy with the episodes that came after the second game, and had meant to create content that pushed technology forward for the IP, not just crank out titles. Half-Life: Alyx sees them return to this principle. This might be a way for them to downplay the part that got side-tracked, continuing the story from a point they think is more viable, or correcting decisions they are no longer happy with.
Nevertheless, for Half-Life: Alyx to have the emotional impact, Valve assumes, or at least suggests, the player to have played through Episode 2.
What are the interactions with the other characters? They should be expecting Alyx to return from the Vault.
Remember, Half-Life: Alyx takes place 5 years before the events in Half-Life 2, and we never see Alyx return from the Vault. After Alyx's ending, the next time we'll encounter her is when she saves Gordon from the Metro Cops in City 17.
What's most interesting to me - I came to realize while writing this - is why the G-Man tells Alyx that he has become dissatisfied with the performance of what is presumably Gordon:
"A previous hire [here the G-Man conjures a crowbar into his right hand] has been unable, or unwilling, to perform the tasks laid before him. We have struggled to find a suitable replacement"
This is remarkable, because the last thing we see in Half-Life, the game that precedes Alyx in time, is the arrangement Gordon makes with the G-Man to start working for the G-Man's employers. At least, that was considered the canonical ending, and the premise that Half-Life 2 builds on.
Taking this into consideration, Half-Life: Alyx might actually take place after Gordon's refusal of the offer, and his subsequent teleportation to an area full of Grunts (whence he could have been saved by Vortigaunts).
But is the G-Man actually talking about Gordon? We briefly see him appearing behind the G-Man to take over the crowbar he's holding, but why would he pick it up if the G-Man is displeased with his work? Does this suggest a third agent, active in the time between Half-Life and Half-Life: Alyx, who had complicity in the imprisonment of the G-Man?
1: See also this article. It explains why Episode 3 was never made, and the gist of it is that Valve claims they want to create revolutionary content, in which creativity in writing and storytelling seems to dominate, whereas their episodic model felt like they were pushing out run-of-the-mill material.
2: The Resonance Cascade - a 'quantum event' - caused the first game's Black Mesa incident, which lead to the Seven Hour War. The bulk of Half-Life 2's playtime is caused by a faulty transporter. Half-Life: Uplink takes place in an alternate timeline. It is well-known that the Portal series takes place in the same universe - titles which hinge on the manipulation of time and space. Apart from the G-Man, we have seen how the Vortigaunts are equally capable of pulling in and out of space-time, as they were able to rescue both Gordon and Alyx from the clutches of the 'interdimensional bureacrat'. Taking into consideration the out-of-universe explanation, Half-Life: Alyx's plot could just be a very smart way for Valve to right their wrongs and simultaneously introduce us to an even grander overall story arc and more dramatic gameplay changes.
