How do you deal with international partners

We think we have an interesting idea and we would like to execute it. But, we are all in different countries. Canada, The Netherlands, Poland. Borders Schmorders. Working together from different countries and timezones is not the problem. But I am confused about how to setup the legal structure. Who has been in the same situation? What do you do? Or should we simply start with a simple agreement between the partners and worry about legal structures later on?