But if you log into the market using the same account as before then you should see a list of all the apps you had previously and be able to download and install them to your new phone (it doesn't matter if you paid for any, they will be there too and you won't have to pay again)
I'm new to it myself, so I can't tell you where to find this list, sorry.