You've got it backwards, unless static leases have been configured, a DHCP server only keeps persistent state of currently assigned IP addresses the server has committed to, and possible IP addresses that have been offered, but not yet requested by the client. The server commits to an IP address for the duration of the lease time (which is configured at the server), although clients can renew a lease if needed, or until a client release the IP address voluntarily. It is the client that remembers the address previously assigned to it and re-requests it from the DHCP server.
Typically, when a client first joins a network, it broadcasts DHCPDISCOVER messages on the local physical subnet. DHCP servers on the subnet respond with DHCPOFFER messages containing a number of configuration options, including the IP address offered. The client responds with a DHCPREQUEST message to a particular server, asking to reserve the offerred IP address. The server either acknowledges the lease with a DHCPACK message, or a DHCPNAK (negative acknowledgement) in case it is not able to satisfy the lease specified in the previously received DHCPREQUEST (e.g. the address has been leased to another client in the meantime).
If the client remembers an IP address previously allocated to it, it may skip the DHCPDISCOVER step and broadcast a DHCPREQUEST message requesting the previous address on the local subnet. Servers with knowledge of the client's configuration parameters respond with a DHCPACK. If the client's request is invalid (e.g. the client has moved to a new subnet) servers respond with a DHCPNACK.
Note that while the servers maintain state of what IP addresses they have assigned, it is not their responsibility to determine if the IP address requested by a client in fact is unused. If the client detects (e.g., through the use of ARP) that the address it requested (and received an acknowledgement for) is already used, it is mandated to decline the address by sending a DHCPDECLINE message to the server.
The DHCP protocol is defined in RFC 2131. Client-server interaction is detailed in section 3.1. Reusing a previously allocated network address is described specifically in section 3.2.