presentViewControllerを使った画面遷移で遷移先でナビゲーションバーを付けたい

presentModalViewControllerが非推奨になっているとのことで、実現方法や検索ワードがわからず詰まっているのでお力をお貸しいただきたいです。

// 現在は以下のメソッドで同じことができます
@available(iOS 5.0, *)
public func presentViewController(viewControllerToPresent: UIViewController, animated flag: Bool, completion: (() -> Void)?)

アプリケーションのヘッダーはすべて、UINavigationControllerでしかつくれないのでしょうか？また、その方法が一般的なのでしょうか？

UINavigationControllerは階層的な画面遷移を管理するクラスです、NavigationControllerを使用してもヘッダーは非表示にできるので自分で好きに作成することができます。
NavigationBarはカスタムもできるので、そちらに自分のデザインを当てはめるのが簡単で、一般的だと思います。

navigationControllerのpushViewControllerからCoverVerticalのアニメーションを付けて簡単にページ遷移することはできないのでしょうか？

以下の書き方がその例になると思います。

import UIKit

class ViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
    }

    @IBAction func openModalView(sender: UIButton) {

        // 遷移先のViewControllerを生成
        let modalViewController = ModalViewController()
        // NavigationControllerのrootViewに遷移先のViewを設定
        let navi = UINavigationController(rootViewController: modalViewController)

        // トランジションを指定したい場合は以下の行を追加
        // navi.modalTransitionStyle = .FlipHorizontal
        presentViewController(navi, animated: true, completion: nil)
    }

    override func didReceiveMemoryWarning() {
        super.didReceiveMemoryWarning()
    }
}

// 遷移先のViewControllre
class ModalViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
        self.view.backgroundColor = UIColor.yellowColor()
        self.title = "NextViewController"

        let closeButtonItem = UIBarButtonItem(title: "Close", style: .Plain, target: self, action: #selector(ModalViewController.close))
        self.navigationItem.leftBarButtonItem = closeButtonItem
    }

    func  close() {
        dismissViewControllerAnimated(true, completion: nil)
    }
}

コードで書いている例をStoryboardで表すと以下の様になっています。