You generate the SSH key (which includes both a public and private key) on the client, then upload the public half to the server (so it can validate your identity; by knowing the public part of the key, the server can validate your identity by decrypting something encrypted with the private half), and keep the private half private. (usually that means protecting it with a passphrase)
See more information here, on the GitHub site. While that information is specific to GitHub, the process is going to be similar for any git server (or SSH, or any service utilizing SSH, for that matter). For instructions specific to Ubuntu, see this question on the Ask Ubuntu site.