Você está tentando dar um push, mas teu repositório local não está sincronizado com o remoto.
Você tem que fazer o merge dos teus commits com os que foram pro repositório depois de você clona-lo.
Por exemplo, imagine que o repositório tem esses commits:
Remoto: A -> B -> C
Você fez o clone, tem uma cópia exatamente igual na tua máquina:
Local: A -> B -> C
Você fez um commit novo, o local ficou assim:
Local: A -> B -> C -> D
Nesse meio tempo, enquanto você fez o commit D, alguém deu um commit no remoto, deixando-o assim:
Remoto: A -> B -> C -> E
Você agora está tentando dar push no teu A -> B -> C -> D , e o remoto está diferente. Existe um conflito, porque na tua máquina, de C vai para D, e na do servidor, de C vai para E. Você precisa dar merge nos commits D e E.
Primeiro passo:
git fetch
Esse comando vai baixar o conteúdo do repositório local para tua máquina. Se você quiser ver as branchs, digita assim:
git branch -va
Vai aparecer a branch remota, algo mais ou menos assim: remotes/<nome_do_repositorio>/<nome_da_branch>.
Na tua branch local, você vai fazer isso:
git merge remotes/<nome_do_repositorio>/<nome_da_branch>
Por exemplo: Se o teu repositório remoto é apelidado de origin e a branch é a master, você vai fazer algo assim
git merge remotes/origin/master
Certo? Se não exisitrem conflitos, vai ser de boa. É só digitar git push para subir as mudanças para o repositório remoto. Caso hajam conflitos, você vai ter que resolve-los e terminar o commit do merge, podendo então fazer o push.
Outra maneira de fazer isso, é utilizando git pull. O pull nada mais é do que fetch e uma tentativa de merge. É só um atalho para você. O pull vai fazer o que eu disse pra você fazer nesse passos anteriores.