There's an additional field in the DHCP header to indicate the IP address of the relay agent. This will be the address of the interface upon which the router/relay agent receives a DHCPDISCOVER from a client. More importantly, this address informs the DHCP server of which DHCP pool it should offer an address from.
The DHCP address for the client is not bound to the relay agent as well -- the DHCP server is only using its knowledge of the relay to supply the correct address. Take a look at the diagram here as well, depicting the client/relay/server relationship.
Note the MAC address of our "host":
Host#show int gi0/0
GigabitEthernet0/0 is up, line protocol is up
Hardware is iGbE, address is 0c79.14cc.1500 (bia 0c79.14cc.1500)
This is the DHCPDISCOVER being relayed, with the client MAC address and relay agent IP address:
And this is the DHCPOFFER as it returns to the host:
So yes, the relay does make a change to the packet by inserting its address in the relay agent field, but that isn't part of the binding issued by the server. The only binding that exists is between the DHCP server and the client.
The relay does not need to remember any associations as it's simply broadcasting replies (OFFER/ACK) from the DHCP server onto the appropriate connected network, where the clients reside. (Which it can determine via seeing which relay address is specified.)
Also for future reference, when I get stuck on understanding exactly what a protocol is doing, I find it's best to configure it in GNS3 and do a few packet captures. Then reference what you see with what you're reading.