Work permit common law proof does not have to be as extensive as immigration common law proof.
Here is what it says in the instruction guide for a work permit at http://www.cic.gc.ca/english/information/applications/guides/5487ETOC.asp :
A common-law partner
Refers to a person who is living in a conjugal relationship with another person (opposite or same sex), and has done so continuously for a period of at least one year. A conjugal relationship exists when there is a significant degree of commitment between two people.
Common-law partners must attach any documents that show they are in a committed and genuine relationship, for example, evidence that they share the same home, that they support each other financially and emotionally, that they have had children together, or that they present themselves in public as a couple.
Common-law partners who are unable to live together or appear in public together because of legal restrictions in their home country may still qualify and should be included on the application.
Common-law partners who meet the conditions outlined above but who have been separated for reasons beyond their control (for example, civil war or armed conflict) may qualify and should be included on the application.
If you were able to get a work permit with a working holiday program, each of you would be on your own. If you find a job and get a work permit that way, if the job is skilled, the other person can apply for an open work permit based on the partners work permit.