What's the difference between all the Selection Segues?

Here is a quick summary of the segues and an example for each type.

Show - Pushes the destination view controller onto the navigation stack, sliding overtop from right to left, providing a back button to return to the source - or if not embedded in a navigation controller it will be presented modally
Example: Navigating inboxes/folders in Mail

Show Detail - For use in a split view controller, replaces the detail/secondary view controller when in an expanded 2 column interface, otherwise if collapsed to 1 column it will push in a navigation controller
Example: In Messages, tapping a conversation will show the conversation details - replacing the view controller on the right when in a two column layout, or push the conversation when in a single column layout

Present Modally - Presents a view controller in various animated fashions as defined by the Presentation option, covering the previous view controller - most commonly used to present a view controller that animates up from the bottom and covers the entire screen on iPhone, or on iPad it's common to present it as a centered box that darkens the presenting view controller
Example: Selecting Touch ID & Passcode in Settings

Popover Presentation - When run on iPad, the destination appears in a popover, and tapping anywhere outside of this popover will dismiss it, or on iPhone popovers are supported as well but by default it will present the destination modally over the full screen
Example: Tapping the + button in Calendar

Custom - You may implement your own custom segue and have control over its behavior

The deprecated segues are essentially the non-adaptive equivalents of those described above. These segue types were deprecated in iOS 8: Push, Modal, Popover, Replace.

For more info, you may read over the Using Segues documentation which also explains the types of segues and how to use them in a Storyboard. Also check out Session 216 Building Adaptive Apps with UIKit from WWDC 2014. They talked about how you can build adaptive apps using these new Adaptive Segues, and they built a demo project that utilizes these segues.

For clarity, I'd like to illustrate @Joey's answer above with these gifs :

Show

Show Detail

Present Modally

Present As Popover

The document has moved here it seems: https://help.apple.com/xcode/mac/8.0/#/dev564169bb1

Can't copy the icons here, but here are the descriptions:

• Show: Present the content in the detail or master area depending on the content of the screen.

  If the app is displaying a master and detail view, the content is pushed onto the detail area. If the app is only displaying the master or the detail, the content is pushed on top of the current view controller stack.

• Show Detail: Present the content in the detail area.

  If the app is displaying a master and detail view, the new content replaces the current detail. If the app is only displaying the master or the detail, the content replaces the top of the current view controller stack.

• Present Modally: Present the content modally.

• Present as Popover: Present the content as a popover anchored to an existing view.

• Custom: Create your own behaviors by using a custom segue.