A couple weeks ago it was discovered that users running the iPhone OS 3.0 beta were unable to redownload purchased iPhone applications.
The mobile App Store presented a message stating, "You've already purchased this. You can redownload it for free on your computer, or tap Buy to buy it again."
AppAdvice discovered that this message only occurred to users who had not updated to the new iTunes 8.2 software. This new version adds some logic that tells a device what iTunes accounts are authorized on the computer. Since those users devices never received the authorization information from iTunes 8.2 they were not able to pass it along to the App Store when they tried re-downloading apps.
So in order to redownload apps you must have installed iTunes 8.2 and have synced to a computer that has been authorized with your iTunes account.