To give you a bit of an overview so you can find out more elsewhere.
What makes a company, a company in the eyes of the law?
Once upon a time (warning: pseudo-history to explain the legal concept), Her Majesty would hand out letters patent to a group of individuals -- a 'company', if you will -- formally creating the company and granting them privileges as a company such as limited liability or a monopoly on tea. Creating a legal person out of a group of natural persons 'creates' a 'body', which came to be called 'incorporation', with companies also known as corporations.
Today the process is more routine. You fill out some forms and pay a fee and, under legislation such as the Corporations Act 2001 (Cth) (in Australia, for example), a government authority will create a company for you.
The upshot is that a company does not exist unless the government says it does. (And note that in a federation, such as Canada, it can be either the state/province or the federal government that creates a particular company.)
You would go to your accountant who would go to a government authority who would register your company, allocating it a name and a number. And then it would exist.
A foreign jurisdiction may or may not recognise your Canadian company. It may require you to register as a foreign corporation before doing business there. Each jurisdiction is different.
If your company does not exist or is not recognised, then you are left with bare individuals. That means no limited liability.
I was wondering first of all when is the best time to make the startup a company? (Right at the start? When the product is done and available? As soon as money gets involved?)
This question is mostly business advice rather than a law question. Get proper advice.
To give you an indication of the kinds of issues involved, the timing of the creation of the company is important for reasons such as tax. For example, the company will probably end up owning intellectual property. If you develop the property as an individual and transfer it to the company later, you may (subject to any applicable tax concessions) have to pay tax on its value at that time. For that reason creating the company and putting intellectual property into it earlier may suit you best. But get actual advice on that.