Distributed database, the local cell knows which handsets it has had recent contact with and where it has not handed them off to another base station ( it polls those units that are not active every few minutes which is that common chirp you get from a phone near sensitive electronics when you do not have a data channel active) so it reports this to a local master database. the incoming call results in a lookup for location, starting first in the local cells then moving out to cells further out in the network ( making use of the fact that you typically call a phone near your location or the gateway into the local part of the cell network) then finally using a database of phones that are known to be roaming off the network. If no result then it will either go to voicemail ( if set up) or the subscriber unavailable message.
Typically the far databases will take too long to respond to the request, but will return a reply if it is available, which is cached. Thus if you try again within a short time the call will go through.