リモートリポジトリを、ローカルに登録するときうまくいかず、
$ git push -u origin master
remote: Invalid username or password.
fatal: Authentication failed for 'https://github.com/...
となりログインできません。

$ ssh -T git@github.com
The authenticity of host 'github.com (13.114.40.48)' can't be established.
RSA key fingerprint is ...
と表示されるのでssh接続が必要なのでしょうか。

いえ、ssh接続は必要ないです。

単純にアカウントが間違っている気がしますが、
以下のコマンドで、確認してみて、どうでしょうか。

git remote -v

$ git remote -v
origin https://MadeInJoke1987:PASS@github.com/MadeInJoke1987/searchman.git (fetch)
origin https://MadeInJoke1987:PASS@github.com/MadeInJoke1987/searchman.git (push)


上記のように出ました。
ただ、パスワードの一部に%を使っていたので、Githubの方でパスワードを変更しました。こちらにはその変更が反映されていません。

> ただ、パスワードの一部に%を使っていたので、

そのあたりが原因かと思います。
見直してみましょう。