If they're both Android phones, then most applications will be automatically reinstalled on the second phone via Google and the Market. However, not all of them are necessarily always re-installed.
I recommend installing the AppBrain application on the original phone, sending the list of all applications currently on that phone, then re-downloading the application on the second phone and installing the apps that are on that list. I haven't used the AppBrain application yet myself, but I'm currently creating a list on their site for when my Droid X arrives in the mail.
For contacts, I recommend simply using BackItUp if both phones are Verizon Wireless phones. If they belong to two different carriers, I don't know if there's anything you can do other than write stuff down manually or something. It depends on the options that you get from the carrier of the original device.
Settings are probably going to be quite different on both phones, even if they're both Android phones. They might not, but it's more likely that they will.
As far as things like audio, pictures, and video are concerned: You should just copy all of that media over to a memory card or to your computer. You can then put it on the second phone.
If there's anything else that needs transferring over, that I didn't mention, please let us know.
