The main cost is hiring an accountant to do the tax return for you. Or figuring out how to do it yourself using software like TaxTron.
If you have employment income + your side project involves a lot of ongoing losses then it may be a good idea to use a partnership or sole proprietorship for tax reasons.
Talk to your lawyer/accountant. There are fewer lawsuits here so you may decide a sole proprietorship (unincorporated business) is fine. Each province has some equivalent of a "Master Business License" that allows you to use a name other than your own for business purposes (so you can cash cheques, etc.).
To conclude (for Canada): generally startups go with a corporation. Side projects might be a corporation, a partnership or a sole proprietorship.