In order to decide which verb (avoir or être) when conjugation the passé composé, you must first choose the verb that you wish to conjugate.
The majority of verbs are regular, and simply use the present tense conjugations of avoir (ex. J'ai trouvé.) However, there are certain verbs which must use être as the auxiliary verb in order to construct the passé composé. The most common verbs in this set have been listed in various ways, but the most common way is MRS VANDERTRAMP, (Monter, Retourner, Sortir, Venir, Aller, Naítre, Descendre, Entrer, Rester, Tomber, Rentrer, Arriver, Mourir and Partir.) This list of verbs uses the present tense conjugation of être as its auxiliary verb (ex. Je suis arrivé(e).) All verbs which are reflexive also use être as the auxiliary verb (ex. Je me suis amusé(e).)
Another point to note is that when a verb uses être as the auxiliary, it must also agree with the gender of the person who is acting the verb out. For example, as a man, I can say 'Je suis allé au cinéma', but if I was referring to a girl, I would have to say 'Elle est allée au cinéma.' The agreements are simple to remember, and follow the normally general rule of adding an 'e' or 's' where the subject is feminine or plural or both.