Should I create a new database for each company?
Yes - Don Dickinson was on the money. However, see a refinement below.
Or should I use one database with tables that have a prefix of the
company name?
Lord no! Changing your database queries for different for client would make you go insane! Also, you'd almost certainly run dynamic SQL (where the table name is changed in code before running the query), which would harm performance as most servers like to cache query plans and interim results - this doesn't work if the table names keep changing.
Or should I Use one database with one
of each table and just add a company
id field to the tables?
You might want to do this if you want to have some kind of scalable model for your customers. Whilst provisioning a new database for each customer gives you lots of flexibility, it also involves costs and complexity. You have to create a new backup schedule, have a lifecycle model for dealing with expired customers etc.
So, you might say that "free trial" and "bronze" customers are all lumped into a single database, using the company id to separate them out; "silver" users get their own database (but you still keep the customer_id field in the schema, so you don't have to change queries between two levels of customer), and "gold" customers get their own database server.
I did something similar a few years ago at a SaaS company - and customers are typically happy to have an upgrade path on infrastructure (read: performance and resilience) as well as features.