I submitted everything according to IRCC's document checklist, which you can generate for yourself here depending on your home country (some countries require additional forms and documents compared to others):
https://ircc.canada.ca/english/information/applications/spouse.asp. It's really important to read their guide carefully. There are a lot of documents that you'll have to submit, but as long as you follow their instructions it is very straightforward. And yes, one of the things required is a police certificate from every country you spent more than 6 months in since turning 18. Each country will have its own instructions for how you get that police certificate.
You'll see on the checklist that you will have to submit documents that indicate your status in Canada. I was out of status from overstaying a study permit, so for this section I submitted a copy of my expired study permit along with a very short letter (1 or 2 paragraphs) explaining why I went out of status.