It's not that hard assuming you've been living together for quite some time.
The CIC defines common law status as any relationship in which the couple has been living together for at least one year. I recently applied for permanent residence, and I filed under common law status. I had to send a lot of documents to prove it: a copy our lease, a statutory declaration of common law union, notarized letters from family and friends, pictures, post-cards, emails, phone records, a letter from our landlord, etc. It's safe to assume the CIC will require this type of evidence if your boyfriend decides to apply for an open work permit.
Here's the definition straight from Canada Revenue:
Hope this helps.