First, create a new local branch and check it out:
git checkout -b <branch-name>
The remote branch is automatically created when you push it to the remote server:
git push <remote-name> <branch-name>
<remote-name> is typically origin, which is the name which git gives to the remote you cloned from. Your colleagues may then simply pull that branch.
Note however that formally, the format is:
git push <remote-name> <local-branch-name>:<remote-branch-name>
But when you omit one, it assumes both branch names are the same. Having said this, as a word of caution, do not make the critical mistake of specifying only :<remote-branch-name> (with the colon), or the remote branch will be deleted!
So that a subsequent git pull will know what to do, you might instead want to use:
git push --set-upstream <remote-name> <local-branch-name>
As described below, the --set-upstream option sets up an upstream branch:
For every branch that is up to date or
successfully pushed, add upstream
(tracking) reference, used by
argument-less git-pull(1) and other
commands.