Le participe passé, utilisé pour le passé composé (on peut aussi l'utiliser comme épithète, et l'accord suit alors la règle pour les adjectifs), s'accorde avec le nom (ou pronom) auquel il se rapporte.
Quand le verbe appelle l'auxiliaire être, le participe passé se rapporte au sujet, et s'accorde donc avec lui.
ex : le bateau est parti.
"parti" est une qualité de "bateau" et s'accorde donc avec lui.
Quand le verbe appelle l'auxiliaire avoir, le participe passé se rapporte au COD.
ex : j'ai mangé une pomme.
"mangé" est une qualité de "pomme". Utilisé comme épithète, le participe passé serai alors "une pomme mangée".
La seule subtilité est que le participe passé (non épithète) ne s'accorde avec le nom ou pronom auquel il se rapporte seulement si celui-ci a déjà été cité dans la phrase, selon l'idée "qu'on ne peut pas faire l'accord si on ne sait pas encore de quoi ça parle".
Donc "j'ai mangé une pomme" mais "la pomme que j'ai mangée".
Voilà, c'est tout, l'accord se fait avec le terme auquel le participe se rapporte pour autant qu'on sache comment l'accorder au moment où on l'écrit. Rien de bien extraordinairement tordu en fait.