The "Deletion Cycle" of a domain name ranges from as short as 36 days to as long as 80 days. The entire cycle and the various statuses are as follows:
EXPIRED: A domain name that has expired can stay in the Expired status from 1 to 45 days. 45 days is the maximum. Most Registrars use between 28 and 45 days for their Expired status. A domain name in the EXPIRED status can still be renewed quickly and inexpensively for the cost of a one year registration.
REDEMPTION GRACE PERIOD (RGP): After a domain name has been through the EXPIRED status it falls into RGP where is remains for 30 days. This period is ICANN mandated and cannot be shortened. Once a domain name falls into RGP it becomes much more expensive to retrieve and renew. Expect to spend upwards of $100US and as much as a week to "redeem" a domain name that has fallen into RGP.
PENDING DELETE: After the RGP a domain enters the PENDING DELETE status and cannot be renewed or redeemed. Domain names are PENDING DELETE for 5 days. After five days the domain name will be released to the public and anyone can register the name. You may be able to wait and register it upon release. Be aware that if your domain name is popular it may be snapped up by one of the many "back-order" companies like SnapNames.com. You are free to use such services to attempt to recapture your domain name as well.