I have a local Git repo that I would like to push to a new remote repo (brand new repo set up on Beanstalk, if that matters).
My local repo has a few branches and tags, and I would like to keep all of my history.

It looks like I basically just need to do a git push, but that only uploads the master branch.

How do I push everything so I get a full replica of my local repo on the remote?

To push all your branches, use either (replace REMOTE with the name of the remote, for example "origin"):

git push REMOTE '*:*'
git push REMOTE --all

To push all your tags:

git push REMOTE --tags

Finally, I think you can do this all in one command with:

git push REMOTE --mirror

However, in addition --mirror, will also push your remotes, so this might not be exactly what you want.