I upvoted two other answers, but I think the way to think of this is simple: You can be on a branch that doesn’t exist. That’s normal in a new empty repository, too, because for a branch name to exist, that branch name must identify the hash ID of an existing, valid commit. A new empty repository has no commits, so no branch names are allowed to exist yet.
Nonetheless, you are, initially, on some branch. The branch you are on is the one whose name is stored in the special name HEAD. In a new, empty repository, Git stores the name master (more precisely, refs/heads/master—the full name of the branch) in HEAD, so you are on master, while master does not exist.
You can change which non-existent branch you are on using git checkout -b:
$ git init
Initialized empty Git repository in [path]
$ git checkout -b asdf
Switched to a new branch 'asdf'
$ git checkout -b hello
Switched to a new branch 'hello'
Whenever you are on a branch that does not exist, the next commit you make creates the branch. This is also how git checkout --orphan works.