How should I connect my replacement 3-way switches?
First off, the wiring of the existing setup looks totally normal as depicted in the diagram.

It looks like you can use these new switches in the current wiring setup. But first it is necessary to understand the connections of the two right cables shown in the upstairs switch box. One of these goes off to the light fixture and the other is the incoming power cable.


Cut the power at the circuit breaker box and make 100% sure that the power is off with a non-contact circuit tester. Also good to verify with a volt meter as well.
Remove the twist on wire connector that joins the two black wires in the upstairs box. Also remove the black wire that connects to the current upstairs switch Common terminal. Make sure you position all the wires so that they are not going to touch and are safely away from any other terminals or the electrical box and grounds. Next step is to identify which of the two right most black wires comes from the power panel circuit breaker and which one goes to the light fixture. The safest way to do this is to use a wire tracer tool from the light fixture box. The alternative, but less safe, is to temporarily turn the power back on and use a volt meter to see which of the two black wires becomes energized with the AC mains voltage. Once determined turn the power back off and/or remove the wire tracer. Mark the correct cable as LIGHT and the other as POWER so as to not confuse which is which. 
You will use the AUX switch in the downstairs location. Remove the old switch and connect the new one as follows: Red to Traveler terminal - White to Neutral Terminal - Safety Ground to switch ground and Black will be capped off and not used.
The RELAY switch will be used in the upstairs location. Remove the old switch and then follow the steps below to connect the new relay switch.
Note that I will refer to your two right most cables as the LIGHT cable and the POWER cable as you determined and marked in step 2. As drawn in your diagram the left cable is the one that routes to the downstairs switch box.
Connect the white wires of all three cables together along with a white pigtail. This will be a wire nut that has four wires in it. These will now connect the neutral of the incoming power cable to neutral for the upstairs switch, to the neutral return from the light fixture and neutral for the upstairs relay switch on the pigtail.  
Connect the other end of the white pigtail to the Neutral terminal on the relay switch.
Connect the safety Ground from the relay switch into the three ground wire connections in the box from the three cables. 
Connect the red wire to the Traveler terminal on the relay switch.
Connect the black wire from the marked POWER cable to the Line terminal on the relay switch. This should connect to nothing else.
Connect the black wire from the marked LIGHT cable to the Load terminal on the relay switch. This should connect to nothing else.
The black wire in the left most cable will not be connected to anything and should be capped off.


That should do it. You can double check your work, mount the switches to the box and restore power to the circuit.