How does AES-GCM produce different ciphertexts, and how can the algorithm decrypt the values if they're random? The title explains it. How does AES-GCM (or other modes for that matter) generate random ciphertexts per execution, and how does the algorithm decrypt a random value since the sender randomizes the ciphertext?
If you will look at Probabilistic encryption in Wikipedia, that will explain shortly. 

GCM mode internally uses CTR mode and therefore let's concentrate on CTR mode. CTR mode converts a block cipher into a stream cipher. In CTR mode, one encrypts the $(nonce\mathbin|counter)$ then x-or the plaintext then increments the counter like 

$$C_i = P_i \oplus E(k, nonce\mathbin|counter+i)$$

If you select a random $nonce$ (IV) for each message, then even if you encrypt the same message you will get different ciphertext.

$$C'_i = P_i \oplus E(k, nonce'\mathbin|counter+i)$$ where $C'\neq C$.

In CTR mode, and therefore in GCM, the nonce must not be reused. It can have catastrophic results from leaking the messages to leaking the authentication key in GCM. 

$$C_i = P_i \oplus E(k, nonce\mathbin|counter+i)$$
$$C''_i = P''_i \oplus E(k, nonce\mathbin|counter+i)$$
x-or both sides and use two-time pad attack as in One-Time Pad.

To prevent the random collision due to the birthday paradox (we expect a nonce collision with 50% probability after randomly selecting $2^{bit-of-nonce/2}$ nonces), incremental IV is advised, that is for each message you next nonce value so that you may prevent the IV re-use.

The nonce is not secret and it is usually prepended to the ciphertext. To decrypt, the other side uses this nonce that you send together with the ciphertext to initialize the mode in the same stage.

The other probabilistic encryption modes like CBC, OFB, etc., similarly uses and IV/nonce to randomize the encryption. 

Note that to have semantically security the probabilistic encryption is necessary.