Relay two SSH connections together

I have three machines:

1. I have physical access to localhost
2. I want to ssh into host1. However, it is behind carrier-grade NAT, so I can't ssh directly to it from localhost
3. relayhost is set up to help me connect from localhost to host1

I want to ssh from each localhost and host1 to relayhost, then have relayhost relay my ssh connection from localhost to host1.

This answer suggests I can create a tunnel on relayhost using ssh -L if I know the URI or IP address of host1. However, I don't know that because of the carrier grade NAT. So I can imagine a process to relay it like this:

1. On host1, ssh user@relayhost
2. relayhost is watching for this connection and when it sees it says "I'm going to create a tunnel from my port 9999 to this connection"
3. On localhost, ssh 9999:relayhost

Is this the right way to go about this? How do I do step 2?

You don't need any specialized triggers on relayhost. All you need to do is use remote port forwarding with ssh -R instead of local port forwarding with ssh -L.

Now if i understand it correctly - your problem is that neither localhost nor host1 have publicly accessible IP - both are behind NAT. Otherwise it would be easier create tunnel from host1 to localhost with ssh -R and then run second SSH connection inside this tunnel.

If we have to use the relay, it can be done in following steps. For clarity let's rename your localhost machine to myhost now.

1. Run this on host1:

   ssh -R 12345:localhost:22 user@relayhost
   

   This will open port 12345 on relayhost and when anyone connects to it, the data will be forwarded to SSH port 22 on host1.

2. Now you can connect to port 12345 on relayhost from myhost.

   ssh user@relayhost -p 12345
   

   In case that you have restrictive firewall on relayhost that prohibits external access to port 12345, you can use local port forwarding to open the port locally on myhost:

   ssh -N -L 56789:localhost:12345 user@relayhost
   

   And then connect to host1 from myhost:

   ssh user@localhost -p 56789
   

However don't expect to build any permanent networking solution on remote port forwarding (see: https://serverfault.com/q/595323 for future possible problems). You should consider using VPN with server on relayhost for long term setup instead.