If you don't already have a Heroku account, create one, it's free. Then install the Heroku gem.
Basic Octopress setup
First make sure you've installed the Heroku gem
Next create a heroku app for deployment. If this is your first time using Heroku, this command will ask for your account credentials, and automatically upload your public SSH key. If you don't already have a public key follow Github's guide and create one.
This will create a new Heroku app for you to deploy to and add a git remote named 'heroku'.
.gitignore in the root of your repository and remove
public. This will let you add generated content for deploying it to Heroku.
That's it, you just deployed to Heroku. If you want to set up a custom domain check out the docs at Heroku.