Add New "Company" to Database Program

We're developing a program that allows users to create "new companies".
Each company will access the same set of tables in the program but each
company must have a unique set of records tied to that company. How do we
accomplist this? Using BatchMove? on the fly? Designating a unique company
ID primary key and adding  referential integrity link field in every table?

Please help! Thanks in advance.