1. Find the setting button for your app on Heroku.com
2. Edit your apps name and click 'Rename'

Next, since the directions above use the Heroku website to update the app name, and because you may have other developers contributing to your project, the individual git remotes will also need to be updated.

3. In terminal (still in your apps root directory) run:

$ git remote rm heroku

followed by

$ git remote add heroku git@heroku.com:yourappname.git

You're now good to go!

UPDATE: There is actually a much simpler way to go about renaming your app. Simply run:
heroku apps:rename newname

If you've tackled your CLI fears this is much easier as it allows you to rename your app and updates your remote Heroku repo in one.