How do I do an initial push to a remote repository with Git?

On server:

mkdir my_project.git
cd my_project.git
git --bare init

On client:

mkdir my_project
cd my_project
touch .gitignore
git init
git add .
git commit -m "Initial commit"
git remote add origin youruser@yourserver.com:/path/to/my_project.git
git push origin master

Note that when you add the origin, there are several formats and schemas you could use. I recommend you see what your hosting service provides.