If you want to leave the country with a minor child as a couple, you need to be able to prove that you are the parents (take translated/apostulated birth certificate)
if you travel as 1 parent with a minor child (or child is traveling alone) : you need a notary act to give you permission. Usually it is as a single permission for 1 country. From a certain age (14) it can be a general permission for 3 countries, from 16 it can be a general permission to all countries.
It is a very simple act, any notary can do it.
I notice that -eventhough my daughter is 17 and looks a lot older- that the agent at the passport control, reads every single word in the document, checks the names with the passport etc. They take this very seriously!
once you have a notary, you give him the necessary documents (birth certificate and marriage certificate), he keeps this documents, and each time you travel alone, you call or mail him, he prepares the document, you pick it up (and pay) and you are ready to go. In my experience you don't need to go to the notary together with husband/wife every time.
Hope this helps...