I just updated my iPhone to iOS 5.01 “over the air” without connecting it to a computer. Besides the new notifications, OTA delta updates are probably the most brilliant feature of iOS 5. Score another point for “PC free”.
For those who need directions, just go to Settings > General > Software Update. I think you may also need to be connected to Wi-Fi. Before you download, you will be reminded that it’s best to make sure your iPhone is connected to power, just in case it’s low on batt and dies during the installation process.
Once the update has been downloaded, it will install itself and your iPhone will auto-restart.