Debugging App When Launched by Push Notification

In Xcode < 4.0 (for Xcode >= 4, see answer by delirus below), you can now configure Xcode to attach the debugger to the app after you launch it, instead of launching the app through the debugger. This lets you debug things that vary based on the launch state of your application, such as URL schemes, pasteboards, and push notifications.

1. In Xcode look in the Source bar, and below Targets there will be Executables.
2. Bring up the inspector for your app in executables.
3. Click on the Debugging tab tab in the inspector.
4. Uncheck "Start executable after starting debugger"
5. Check the "Wait for next launch/push notification"

Now when you click debug from Xcode instead of launching the app a window will display telling it is waiting for the app to launch. You then launch the app normally on the phone and Xcode attaches to it

For Xcode 4 you have to:

1. Edit your active scheme via "Schemes" dropdown. (⌘+<)
2. Than choose your product - 'Run MyApp.app' on the left.
3. Select 'Info' tab on the right.
4. And finally choose "Wait for MyApp.app to launch" option.

More here in "Customize Executables in the Scheme Editor" section.

EDIT:
In case you miss logs in GDB, see Louis Gerbarg's comment to his answer.

For Xcode 10, 9, 8, 7 & 6:

1. Select the Scheme on the toolbar (just left of the device you're debugging with)
2. Choose Edit Scheme
3. Select Run in the left panel
4. For the Launch option, select Wait for executable to be launched
5. Close the Scheme Editor and Run your Xcode project

Now you can debug when launching from a notification, custom url or by touching the app icon.