To avoid rendering your device unusable due to a bad upgrade file, iOS does some verification of the download before installing (likely some type of checksum to ensure the download wasn't corrupted and it's for the right device, etc.). Given that your install process fails during the verification process, it's likely that you either got a bad download (possible, although it should try to re-download if that's the case), or the authentication and verification servers that the installer needs to check against are having some problems (not unlikely, given the load they've had since iOS 6 came out).
Best advice is to just wait it out and try later. However if you're impatient, you can directly download the update to your computer and update via iTunes (although if the servers are experiencing issues, it might affect this method as well).
Steps for a direct update
- Go to this page and download the proper file for your device.
- With your device connected in iTunes, open the device page, hold down option (shift on Windows) and click the Update button.
- An Open File dialog should appear. Browse to the
.ipsw file you downloaded in step 1 and open it.
- Your software update should begin normally.