Quite hard to help you there! Yet another difficulty (like nouns' genders) for English speakers indeed, since all past tenses are used with "to have" for you (and yet another thing that makes English easy
)
Native French know if it's "être" or "avoir" for all verbs before they can even read or write. It just sounds unnatural if you mix up the auxiliary, so you can't do the mistake
Twitch's trick could be helpful indeed, still there are exceptions, when a verb can be used with both auxiliaries, in two different meanings of course (argh
