Technical Note TN2265: Troubleshooting Push Notifications
The first time a push-enabled app
  registers for push notifications, iOS
  asks the user if they wish to receive
  notifications for that app. Once the
  user has responded to this alert it is
  not presented again unless the device
  is restored or the app has been
  uninstalled for at least a day.
If you want to simulate a first-time
  run of your app, you can leave the app
  uninstalled for a day. You can achieve
  the latter without actually waiting a
  day by setting the system clock
  forward a day or more, turning the
  device off completely, then turning
  the device back on.
Update: As noted in the comments below, this solution stopped working since iOS 5.1. I would encourage filing a bug with Apple so they can update their documentation. The current solution seems to be resetting the device's content and settings.
Update: The tech note has been updated with new steps that work correctly as of iOS 7.
- Delete your app from the device.
- Turn the device off completely and turn it back on.
- Go to Settings > General > Date & Time and set the date ahead a day or more.
- Turn the device off completely again and turn it back on.
UPDATE as of iOS 9
Simply deleting and reinstalling the app will reset the notification status to notDetermined (meaning prompts will appear).
Thanks to the answer by Gomfucius below:
https://stackoverflow.com/a/33247900/704803