if you're using a phone with a sim card:
go into the contacts listing on the original phone.
save (or export) contacts
specify to sim card
turn off phone
remove sim card
turn off new phone
put in sim card
turn on new phone
on new phone go into the contacts listing
specify from sim card
you can now turn off your new phone and put the sim card they gave you back in if you wish.
for CDMA phones:
there is a way that you can wirelessly transmit the data between two phones. i know this is what the verizon reps do when you buy a new phone.
if you have a miniusb port you can also use a program called bitpim on a computer to pull/push contacts to cell phones.