What you are asking about is part of what's commonly called "key management." If you google the term, you'll find lots of interesting reading. You may well discover that there are other parts of key management that your solution needs to address, like revocation and rotation.
In the particular part of key management that you're looking at, you need to figure out how to have two nodes trust each other. This means that you have to identify a separate thing that you trust on which to base the nodes' trust. There are two common approaches:
Trusting a third party. This is the model that we use for most websites we visit. When our computers are created, the trusted third party creates the device to already know about and trust certain entities, like Verisign. When we contact a web site over HTTPS, the browser automatically checks if Verisign (or another trusted third party certificate authority) agrees that this is the website that it claims to be. The magic of Public Key Cryptography and how this works is a whole separate topic, which I recommend you investigate (just google for it :) ).
Separate, secure channel. In this model, we use a separate channel, like an administrator who transfers the secret from one node to the other. The admin can do this in any manner s/he wishes, such as encrypted data carried carried via USB stick over sneakernet, or the data can be transferred across a separate SFTP server that s/he has already bootstrapped and can verify that it's secure (such as with his/her own internal certificate authority). Some variations of this are sharing a PGP key on a business card (if you trust that the person giving you the business card is the person with whom you want to communicate), or calling the key-owner over the phone and verbally confirming that the hash of the data you received is the same as the hash of the data they sent.
There are on-line key exchange protocols - you can look them up, probably even on Wikipedia, using the phrase "key exchange", but you need to be careful that they actually guarantee the things you need to determine - like how does the protocol authenticate the other side of the communication channel. For example, Diffie Hellman guarantees that you have exchanged a key without ever exchanging the actual contents of the key, but you don't know with whom you are communicating - it's an anonymous key exchange model.
You also mention that you're worried about message replay. Modern secure communication protocols like SSH and TLS protect against this. Any good protocol will have received analysis about its security properties, which are often well described on Wikipedia.
Oh, and you should not create your own protocol. There are many tomes about how to write secure protocols, analyses of existing protocols and there security properties (or lack thereof). Unless you're planning to become an expert in the topic (which will take many years and thousands of pages of reading), you should take the path of least resistance and just use a well known, well exercised, well respected protocol that does the work you need.