While I'm all for unblocking people's work issues, I don't think "push --force" or "--allow_unrelated_histories" should be taught to new users as general solutions because they can cause real havoc to a repository when one uses them without understand why things aren't working in the first place.
When you have a situation like this where you started with a local repository, and want to make a remote on GitHub to share your work with, there is something to watch out for.
When you create the new online repository, there's an option "Initialize this repository with a README". If you read the fine print, it says "Skip this step if you’re importing an existing repository."
You may have checked that box. Or similarly, you made an add/commit online before you attempted an initial push. What happens is you create a unique commit history in each place and they can't be reconciled without the special allowance mentioned in Nevermore's answer (because git doesn't want you to operate that way). You can follow some of the advice mentioned here, or more simply just don't check that option next time you want to link some local files to a brand new remote; keeping the remote clean for that initial push.
Reference: my first experience with git + hub was to run into this same problem and do a lot of learning to understand what had happened and why.