When you sign in with your google account with your new phone go to the Market, press menu then download, and your apps with be listed there for you to download again at no additional charge.

 

Yes they are tied to your Google account not your phone.

 

I'd be weary about some paid apps though. After I started to reinstall apps on my replacement drive, I noticed that Live Wallpapers I purchased, such as the Mario one, would not transfer, and showed that I would in fact need to pay again to have them.

 

After Froyo install and system reset, my paid apps did not show up in my download list. I reinstalled them and Google duplicated the charges. I can find no way to undo the charges through google so I turned it over to my CC company but feel I am in for more trouble.

 

did you use a different gmail account? I still get apps I paid for with my eris back in december in the market downloads.