以前のOSと比べても全くやり方変わらないのですが、いろいろとちょっと違ったりするので書いておきます。（違わないかも）

インストール

インストールはこれだけでOKです。Ubuntuならサーバー自体をクライアントとして使う場合もあるかと思うのでopenssh-clientも一緒に入れておくとよいと思います。

apt-get -y install openssh-server openssh-client

なんか設定中にいろいろやりすぎて失敗しちゃった場合は、

apt-get -y remove openssh-server openssh-client

で一度削除してからもう一度インストールしなおすとよいと思います。

インストールした時点で起動させてみる

# /etc/init.d/ssh restart
Rather than invoking init scripts through /etc/init.d, use the service(8)
utility, e.g. service ssh restart

Since the script you are attempting to invoke has been converted to an
Upstart job, you may also use the restart(8) utility, e.g. restart ssh
ssh start/running, process 1781

とサービスの方からrestartさせた方がいいみたいなことを言われますので、

# restart ssh

で起動させておきます。たぶんこれで警告はなくなるはず。

sshd_configの設定（ssh_configではないので注意！）

　以下の内容をコピペしちゃっても構わないと思います。ポートはデフォルトの22にしていますが、22じゃない方が無難です。特に立派なファイヤーウォールとかない場合には。

#-----------------------------
# Original Setting for omnioo
#-----------------------------
#------------------
# Oroginal Setting
#------------------
Port 22                    # 任意のポートを指定 22じゃない方が無難
Protocol 2                # 2でいいと思います。
HostKey /etc/ssh/ssh_host_rsa_key    # RSA有効
HostKey /etc/ssh/ssh_host_dsa_key    # DSA有効
UsePrivilegeSeparation yes        # root権限から分離させてプロセスを開始
KeyRegenerationInterval 3600        # 鍵の再生成間隔　このままでよいです
ServerKeyBits 768            # デフォルトのままでよいです。512以下にしない。
SyslogFacility AUTH            # ログのとり方指定(種類）　このままでよいです
LogLevel INFO                # ログのとり方指定（長さ）　このままでいいです
LoginGraceTime 120            # ログインの時間
PermitRootLogin no            # 安全のためrootログインは禁止
StrictModes yes                # 初心者とパーミッション777好きの人はyesに！
RSAAuthentication yes            # ssh1の公開鍵認証を許可
PubkeyAuthentication yes        # ssh2の公開鍵認証を許可
AuthorizedKeysFile    %h/.ssh/authorized_keys        # 公開鍵の保存場所とファイル名
IgnoreRhosts yes                    # .rhostsおよび.shostsファイルを使わない
RhostsRSAAuthentication no                # ssh1のホストベース認証を切る
HostbasedAuthentication no                # ssh2のホストベース認証を切る
PermitEmptyPasswords no                    # パスワードが空の認証はできない
ChallengeResponseAuthentication no            # チャレンジレスポンスはしない
PasswordAuthentication no                # パスワード認証の設定を切る（ssh1とssh2共通）
X11Forwarding no                    # 基本的にX11の転送はしない
X11DisplayOffset 10                    # 上記でnoなのでコメントアウトしてよし
PrintMotd yes                        # /etc/motd(お知らせファイル）の表示
PrintLastLog yes                    # 前回のログインの日付表示
TCPKeepAlive yes                    # 幽霊ユーザー防止
AcceptEnv LANG LC_*                    # 環境変数の受け渡し
Subsystem sftp /usr/lib/openssh/sftp-server        # sftp-server使用可
UsePAM no                        # PAM認証しない

##### END

設定が終わったら、

# restart ssh

で、

# update-rc.d ssh defaults

もやっておくといいです。OS起動時に自動的にSSHも起動する設定。

接続テスト

$ ssh username@localhost

とやってみると一応接続できる筈です。ポートを22以外で設定している場合は、

$ ssh -p xxxx username@localhost

という風にやります。キーなんかの設定をしていないので接続はできないんですが、一応ポートも通ってSSHも動いていることが確認できます。
実際はこんな風になってしまう。

The authenticity of host 'localhost (::1)' can't be established.
RSA key fingerprint is bb:80:w2:20:05:66:2f:ds:cb:ff:40:79:7a:6f:d6:8c.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added 'localhost' (RSA) to the list of known hosts.
Permission denied (publickey).

キーの作成

 Windowsには便利なクライアントソフトがいっぱいあるので割愛。私はMacしか使わないのでMacの方の設定をします。

RSAキーの作成

 Macの端末（ターミナルでしたっけ？）を開いて、以下のコマンドで設定してゆきます。ターミナルはアプリのユーティリティーに入っていたと思います。

$ ssh-keygen -t rsa　//rsaのキーの作成
Generating public/private rsa key pair.
Enter file in which to save the key (/Users/username/.ssh/id_rsa): id_rsa  //このパスにid_rsaというファイルでキーを保存する
id_rsa already exists.   //以前のものが残っていたら上書きするかどうか聞いてくるので任意で。
Overwrite (y/n)? yes
Enter passphrase (empty for no passphrase):　　//パスワード入力
Enter same passphrase again:　　　　　　　　　　//もう一度パスワード入力
Your identification has been saved in id_rsa.
Your public key has been saved in id_rsa.pub.
The key fingerprint is:
33:3d:6a:29:4a:93:f0:77:ec:91:37:e8:ec:xx:xx:xx username@Mac.local
The key's randomart image is:
+--[ RSA 2048]----+
|                 |
|                 |
|                 |
|         .       |
|  .     S o      |
|   o . . B .     |
|    = o Xxx      |
|   . + B.ss.     |
|    . .+*oD      |
+-----------------+

こんな感じで作成終了。

DSAキーの作成

$ ssh-keygen -t dsa  //dsaのキーの作成
Generating public/private dsa key pair.
Enter file in which to save the key (/Users/username/.ssh/id_dsa): id_dsa  //このパスにid_dsaというファイルでキーを保存する
Enter passphrase (empty for no passphrase):  //パスワード入力
Enter same passphrase again:                 //再度パスワード入力
Your identification has been saved in id_dsa.
Your public key has been saved in id_dsa.pub.
The key fingerprint is:
4c:53:4d:44:63:4b:eb:d7:d5:a5:65:9c:1f:xx:xx:xx username@Mac.local
The key's randomart image is:
+--[ DSA 1024]----+
|          .=R  +G|
|         . o.+.X+|
|        o   o + %|
|       o . . A .o|
|        D   . . .|
|             .   |
|                 |
|                 |
|                 |
+-----------------+

　私はRSAキーを使っているのでDSAキーは作らなくていいのですが、一応参考に。

キーの設定

　.sshという風に一応隠しディレクトリになっていますが、cdなんかで移動して表示させます。作成したファイル群の確認をします。

$ ls -l
-rw-------  1 oosamuuy  staff   736  8 26  2010 id_dsa
-rw-r--r--  1 oosamuuy  staff   629  8 26  2010 id_dsa.pub
-rw-------  1 oosamuuy  staff  1743  8 26  2010 id_rsa
-rw-r--r--  1 oosamuuy  staff   421  8 26  2010 id_rsa.pub
-rw-r--r--  1 oosamuuy  staff  1991 12 13 22:19 known_hosts

　それぞれのキーに.pubなる公開鍵が作成されています。id_rsaが秘密鍵でid_rsa.pubが公開鍵になります。これらはペアで作成されてペアで使います。DSAも同様です。で、known_hostsに接続したsshの情報が入ってきます。
　id_rsa.pubの中身を何らかの方法でサーバーの方に転送します。USBメモリでもいいし、メールでもいいし、なんでもいいです。中身は、

ssh-rsa AAAA...（中略）...cOsu0SBiV5J/5h401gCetw== username@mac

みたいな感じになっているのでid_rsa.pubの中身をそのままサーバーに転送します。

　なんらかの方法でサーバーで受け取ったら、

/home/username/.ssh/authorized_keys

にファイルを作ります。不親切で自動的にファイル作ってくれるとかそういう心がないので、自分で作ります。

ch /home/username/.ssh
touch authorized_keys

とか何でもいいので、適当に作って先ほどの公開鍵の文字列をコピペして保存します。geditでもvimでもviでも何でもいいです。これで設定終わりです。

接続

ssh username@<IPとかドメインとか>

で接続すると接続したホストに対してフィンガープリント（指紋）なるものを発行し接続の準備をします。で、yesで答えて、パスワード訊かれてログインできます。2回目以降はパスワードだけでログインできます。