I'm using Heroku and every time I push changes to Heroku, the plugins installed from the plugin store get removed. Do I need to add them to my composer file manually?
This is the way Heroku works with its ephemeral file system. Anything written by the webapp (which includes plugins installed via Composer) after the fact can be wiped out at any time.
If you must ship it on Heroku, you probably should check all of
vendor/ into the repo, so that it's part of the actual deployment, and not added post facto.