Git Fatal Error: info/refs not found

fatal: https://github.com/username/repository-name.git/info/refs not found: did you run git update-server-info on the server?

In GitHub context, this message should be understood as "The repository doesn't exist". You're supposed to push toward an already existing bare repository. A bare repository is a repository without a working directory, usually found server-side.

If I create my repository first on github, then I can push branches no problem. Is this procedure routine?

Yes. You're supposed to first create your repository on GitHub. See the help topic about this

indeed, as stated by the documentation "To put your project up on GitHub, you'll need to have a GitHub repository for it to live in."

I confirm you need to create your repo on GitHub first, before being able to push to said (remote) repo.

Once created, you can add it as a remote named 'origin' to your local repo, and 'git push origin master' (for the first push).