When I fail at battles, my pets faint. It always says, "Go to the healer to heal your pets"... But I cannot find the healer... Help?

Frankly, it's more time consuming but infinitely cheaper to just take the pets in question out of the party and wait for the autoheal.

But the Healers can be located in the Plazas of the three towns.
(I remember when I was a newbie, I used so much gold healing at the healers because I didn't know about the autohealing; the amount of gold charged for healing is calculated by the amount of HP the pets need to recover)

Besides finding the healer in the towns, you can also heal your pets from your stable page. It is slightly cheaper than using the healer. I can't remember if you need to remove your pets from your party though, but you probably have to.