Go to the carriers retail store or website and order one. You would need to speak to a customer service rep and request the service to be transferred. You would need to be able to prove your identity and ownership of the device, and have all relevant information handy.
Relevant information is things like the phones IMEI and serial numbers which can be found on a sticker underneath the battery or on the original packaging. Also if the new phone took a SIM card, you would need the SIM card number as well.