The ISP also has a DHCP server, just like your router. The DHCP server may have your old address cached like previous answers posted, and may give you a new address if not.
DHCP sometimes runs directly over your uplink, and sometimes it is terminated at the network equipment that runs the uplinks. In bridged mode, for example, DHCP is used to assign the address directly. For PPP connections (like PPPoA, PPPoE etc.) the DHCP pool is used to supply addresses but the actual configuration is done by the PPP service.
IP-address allocation is pretty much the same for all networks until you reach the RIR blocks.
Basically, you have a globally limited amount of IP addresses, which are divided in to blocks. Those blocks are then given to geographical areas, which in turn are divided in to block which are given to ISP's. IP blocks can be requested when you run out, can be bought form companies, or 'rented' form ISP's.
There are organisations that manage IP allocation to make sure it is known what IP block belongs to someone. It flows like this:
IANA has all of the IP addresses, which get divided in to blocks and those blocks are re-divided by RIR's. A RIR is a Regional Internet Registry. Each RIR covers a geographic area, there are 5 in total. The RIR's in turn divide their IP blocks, and give them out on request to i.e. LIR's and NIR's: Local Internet Registries and National Internet Registries. ISP's and businesses and if I'm not mistaken, individuals, can then request IP addresses from those LIR's or NIR's and in some cases directly form RIR's.
What you do with your block of IP addresses is up to you. To make use of them, it would make sense to make sure the internet knows where your IP address is, on what network, and how to get there. That is done with routers and gateways using protocols such as BGP which makes it possible to let networks communicate to each other so they know they exist and know what networks they make available. But at this point, we're getting past IP-adresses. (if you want to know more, look up Autonomous Systems, peering and BGP)
Most of that information can be found here: http://www.internetassignednumbersauthority.org/numbers
So basically, after a few organisations, a range of IP addresses (a block) is divided and split in to smaller unites down the line and at some point owned by an ISP. That ISP then lets other ISP's know that it has that range of IP addresses so it can be used to communicate. At that point the ISP's network is ready and only needs to allocate a single IP to a client's network which then becomes the client's WAN IP address.
Now, an ISP cannot tell other ISP's that it owns IP addresses it doesn't actually own, because it wouldn't match the registries at the LIR/NIR/RIR level which can be publicly checked (and automatically as well). So at that level, duplicate IP's are not going to happen. When a rogue ISP tries to do that anyway, it pretty much gets disconnected from the rest of the internet by not allowing it to communicate with other ISP's (as they basically pull the plug on the fake ISP's network-connections to their own networks).
This leaves you at the ISP-level of things. Since the ISP knows what addresses it has, and know what clients it has, and on which network connections those clients are connected, it can simply enforce it's rules by not allowing a client to use an IP that is not assigned by the ISP. It simply ignores all internet traffic from a client that's not supposed to be there. Assigning IP addresses as explained at the top is done by a system that remembers who was given what IP address and as such it never gives out the IP address twice.