You can download them again, and paid for ones will be remembered on your google account so you (in theory) don't get charged for them again.
Alternatively, just install ASTRO File Manager. You can make backups of bought apps onto your SD card and save them to HD. So when you get a new phone just drop that folder onto your new phone's SD card and install them.
Also, upon opening the Market after activating your phone, if you click the menu button and clicking "Downloads" for the first time it will show you all previously installed apps paid AND free for you to reinstall them one by one. But ONLY upon the first time opening the downloads on your new or factory rest phone.