Storyboard上でSegueを繋いだ時のトランジションアニメーションを差し替える方法です。
iOSにおけるカスタムトランジションアニメーションはいくつかやり方がありますが、なるべくStoryboardを使う方向性でPushとPopをそれぞれフェードアニメーションに変更してみます

1.CustomSegueを作成する

UIStoryboardSegueを継承しフェードアニメーションを定義したCustomSegueを作成します。
今回はPush用とPop用に２種類用意します

PushFadeSegue.swift

class PushFadeSegue: UIStoryboardSegue {

    override func perform() {
        UIView.transitionWithView(
            (sourceViewController.navigationController?.view)!,
            duration: 0.5,
            options: .TransitionCrossDissolve,
            animations: {
                () -> Void in
                self.sourceViewController.navigationController?.pushViewController(self.destinationViewController, animated: false)
            },
            completion: nil)
    }

}

PopFadeSegue.swift

class PopFadeSegue: UIStoryboardSegue {

    override func perform() {
        UIView.transitionWithView(
            (sourceViewController.navigationController?.view)!,
            duration: 0.5,
            options: .TransitionCrossDissolve,
            animations: {
                () -> Void in
                self.sourceViewController.navigationController?.popViewControllerAnimated(false)
            },
            completion: nil)
    }
    
}

これでアニメーション周りの準備は整いました

2.Push遷移アニメーションを変更する

まずは普通にStoryboardのViewController間でSegueを繋ぎます
今回は下の図のように2つ画面を用意してみました。

ここでSegueに対して変更を加えたいのでSegue（矢印）をクリックしてから右側のInspector内でClassをPushFadeSegueへ変更します

こうなっていればOKです。進むボタンをタップするとフェードアニメーションに変わっているはずです

Kindに関してはCustomの項目もありますがStoryboard上の振る舞いが変わってしまうので今回はPushのままにします（どっちでも大丈夫です）

3.Pop遷移アニメーション

次は戻るアニメーションを変更してみます。
先に戻った先のViewController上にメソッドを用意します

FirstViewController.swift

class FirstViewController: UIViewController {

    @IBAction func unwindToFirstViewController(segue: UIStoryboardSegue) {
    }

}

このメソッドは戻ってきた時にコールされるので特に何もしなければ空でも問題ありません。
メソッド名は引数さえ合っていればなんでも大丈夫です。
※@IBActionを忘れずに付けるようにして下さい

そしてStoryboard上で下の図のように戻るボタン等の遷移元から右クリックでExitへ繋ぎます

すると先ほど作成したメソッド名が現れるはずなので、それをクリックしてリンクさせます

ここまでで戻る遷移は実装できたので画面遷移アニメーションを差し替えます
左側の遷移元のSceneからUnwind segue to "Exit"を選択して右側のInspectorで同じようにClassを変更します。

今回は「戻る」なのでPopFadeSegueを選択します

以上で戻るアニメーションもフェードに変わっているはずです

4.標準の戻るボタンのアニメーションを変更するには

残念ながらこれに関しては明確なやり方は見つかりませんでした。
標準の戻るボタンイベントは簡単にはフックできないので、自前でNavigationBarの左上にUIBarButtonItemを置いて戻るボタンを上書きしてしまうのが手っ取り早いと思います。
もしやり方をご存じの方がいたらコメント頂けると幸いです。

また、Push遷移した時はiOSの画面の左端を右にスワイプすると画面が戻る挙動が標準で付きます。
カスタムアニメーションの種類によってはスワイプで戻れてしまうと違和感が出てしまうこともあると思います。
この機能は標準の戻るボタンと連動しているので自前のボタンで上書きすることでこの挙動を無効にすることが出来ます。この辺の挙動は若干もにょもにょしますね

おわり

ここまででPush,PopともにStoryboardからトランジションアニメーションを変更できます。
魑魅魍魎が蠢くStoryboard周りですが、Apple神への反逆罪で今後リファクタリングの刑に処されないためにもなるべくAppleの意向に沿う形で実装したいものですね（白目）