Proper way to do message encryption between two people with OpenSSL

I want to use OpenSSL to create a way to encrypt a message, authenticate it (to make sure we catch malformed encryption or tampered messages), and to prevent replay attacks on it. I have done some reading and it appears using AES 256 GCM is the right choice since it is AES encrypted via a key, and can provide a HMAC (MAC) to verify against tempering. I have all this currently implemented and working in my project.

What I am wondering about is how to prevent replay attacks. Do I need to incorporate some kind of nonce that increments per message? If so how would I add this nonce into the message or encryption. Would a nonce even help make an encrypted message only be used once?

I basically want to prevent a message being intercepted between myself and another party and being resent. The way I see it AES 256 GCM does not provide a way for preventing this.

Thanks for any suggestions or input.

Edit:: I've been doing some more reading, is the nonce considered the IV which is used during the EVP_(Encrypt|Decrypt)Init_ex call, or is it another piece of data that is added to the message that the application has to choose to accept/reject once decryption is done? If it is the IV I am already using OpenSSLs cryptographically strong pseudo-random byte generator RAND_bytes() for generating my IV.