Originally Posted by Jon Westfall

The app will re-download either automatically, or once you sign in with your Google Account you'll find it under the "Downloads" section of the Android Marketplace, ready to be re-downloaded.

The data is a bit trickier. Some apps support backing it up to the cloud or SD card, which is the best route. However in some cases, the data you've entered is gone unless you have Root and use something like Titanium Backup to grab the app+the data. So a bit easier than WinMo in that you don't have keep the CAB around somewhere, but a bit more annoying if the data wasn't backed up to cloud/SD.

Jon.