公開鍵・秘密鍵を作成する

公開鍵暗号での認証には公開鍵と秘密鍵が必要になります。
秘密鍵は秘密というだけあって**他の人に見られてはいけません。**つまりどこかに送信してはいけません。公開鍵はオーケーです。
秘密鍵は自分で保持し、公開鍵は相手（ここではGitHub)に送ります。
まずは公開鍵と秘密鍵のペアを生成しましょう。

鍵を入れるフォルダに移動しましょう。

$cd ~/.ssh

はじめて鍵を生成するときは何も入っていないはずです。

次のコマンドで鍵を生成します。

$ssh-keygen -t rsa

オプションは付けてある記事も見ますが、このコマンドで十分です。

$ ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/Users/(username)/.ssh/id_rsa):
Enter passphrase (empty for no passphrase):
Enter same passphrase again:

何か聞かれたら3回エンターを押せば、
id_rsaとid_rsa.pubの2つの鍵が生成されます。
なお、2回目、3回目はパラフレーズの設定（パスワード設定のようなもの）ですが、ここはなくてオーケーです。（慣れてきたらパラフレーズの設定もありですが、なくていいでしょう。）
既にid_rsaが存在する人は上書きされてしまうので注意です。

違う名前で生成したいときは

$ ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/Users/(username)/.ssh/id_rsa):id_git_rsa
Enter passphrase (empty for no passphrase):
Enter same passphrase again:

一回目に聞かれたタイミングで名前(ここではid_git_rsa）を指定。
あとはエンターでid_git_rsaとid_git_rsa.pubが生成されます。

ちなみに、名前を指定しない時は勝手に~/.ssh内に鍵を生成してくれますが、上記のように名前を指定するときは~/.ssh内にいないとこの中に生成してくれないので注意です。

公開鍵をGitHubにアップする

https://github.com/settings/ssh
で公開鍵の設定が出来ます。（GitHubに登録していることが前提条件です）

画面右上の「Add SSH key」のボタンを押します。

「title」に公開鍵名、「key」に公開鍵の中身を入れます。

なお、鍵の中身のクリップボードへのコピーは
$ pbcopy < ~/.ssh/id_rsa.pub (Mac)
$ clip < ~/.ssh/id_rsa.pub (Windows)
*鍵の名前は自分の作成したもの。

接続を確かめる

$ ssh -T git@github.com

で返ってきたら接続完了!
Hi (account名)! You've successfully authenticated, but GitHub does not provide shell access.

しかし…
鍵を作るときに名前を指定していれば、うまくいかないかもしれません。
それは、ssh接続の際「~/.ssh/id_rsa」、「~/.ssh/id_dsa」、「~/.ssh/identity」しかデフォルトでは見にいかないからです。
それに対応するためには
~/.ssh/configを作成しその中に

Host github github.com
  HostName github.com
  IdentityFile ~/.ssh/id_git_rsa #ここに自分の鍵のファイル名
  User git

を作成しましょう。
これで、もう一度接続をやってみるとうまくいくはずです。
以下のようにコマンドを打って確かめて見ましょう。

ssh -T github

gitHubとやりとりする

GitHubと実際にやりとりするときにID・パスワードを聞かれるときssh接続がうまくいっていません。
レポジトリのディレクトリに入り

git config remote.origin.url

で確認し　https://github.com/[ユーザID]/[リポジトリ] となっていたら

git remote set-url origin git@github.com:[ユーザID]/[リポジトリ].git

とする。
~/.ssh/configで設定している場合は

git remote set-url origin [Host名]:[ユーザID]/[リポジトリ].git

[Host名]とは~/.ssh/configの一行目のHostの名前（ここではgithub)のことです。

ちなみに、この設定はレポジトリのディレクトリ内の/.git/configで設定出来ます。

[追記] 2015.5.31

上記「GitHubとやりとりする」でssh接続について設定するのは面倒で

~/.gitconfig

[url "github:"]
	InsteadOf = https://github.com/
	InsteadOf = git@github.com:

を追記してあげれば解決でした。
ちなみにpushInsteadOfを使うとpushだけに適用出来るようです。

参考

SSHの公開鍵を作成しGithubに登録する手順
 GithubにSSH接続できない時の対処法
 githubのリポジトリにアクセスするとパスワードを求められる時の対処