If I'm switching from one windows phone to another (replacement), will all my purchased apps from Marketplace be available for download on the new phone or do I have to pay for them again?
All your apps will be available as long as you use the same Live ID to sign in. After you have your Live ID set up go in to the market it will say purchase go ahead and choice that the next screen will say you have already purchased this do you want to install it again.
In fact, go to windowsphone.com and sign in with the same Live account and then click the 'My Phone' link then 'Account' to see a list of all your purchased apps and such. Can even install them from that page.