Rails ではデフォルトでは SQLite が使用されますが、
Heroku では SQLite がサポートされていないので
他のデータベースを使用する必要があります。

https://devcenter.heroku.com/articles/sqlite3

ここで代用が簡単なのが、 PostgreSQLらしい。

Gemfile で Production 環境用に gem 'pg' を追加。

Rails が入っているディレクトリ上で、

heroku addons:add heroku-postgresql

を実行して、PostgreSQLのアドオンを追加。

ただ、それだけだとデプロイ時に、

Invalid DATABASE_URL

って怒られる。

DATABASE_URL という環境変数に
PostgreSQLのURLを指定してやる必要があるらしい。

heroku config

を実行すると出てくる DBのURLを

heroku config:add DATABASE_URL=DBのURL

としてあげればOK。