While in the project, click 'Add Related Company'.
Then start typing in the company's name. If they don't exist in your directory, click 'Create New Business Contact'
Finally, add in the company's information and click 'Save'.
Here's how you can create a new company from within a project.