A few key points to know.
First, you CANNOT recruit during training missions.
Second, there are some units that CANNOT be recruited (like the two Griffons that show up with the Beast Tamer early in chapter 2).
Third, you can use the Chariot Tarot to rewind and try again, HOWEVER, you must do something to change the RNG before trying again (as doing the exact same thing will result in the same outcome). So if you tried to recruit and failed, rewind, then try moving to the other side of the unit and recruiting.
Fourth, you want the unit's health to be as low as possible, and you want to stand next to them for the best chances.

If you have the correct skill, and select a unit that is recruitable you will see this icon:




If you are using the wrong skill OR the unit is incapacitated (such as petrified) you will see this:




If a unit is simply unrecruitable (like bosses and some special enemies) you'll see this icon:





This guide is just intended to cover the basics. I'm sure someone (with more time and patience) could put together a far more detailed guide. But I figured this would be handy for quick reference.

To recruit units, you need the skills tied to their race.

Recruit: Human & Winged
Coax: Lizardman & Lamia
Subdue: Beast (Griffon, Octopus, etc)
Tame: Dragon
Control Golems: Golem & Pumpkin
Master Undead: Skeleton & Ghost
Demon's Pact: Orc, Imp & Zombie (though Zombies are technically Undead, they don't count as them for recruiting)
Fey Pact: Fairy
Seraph's Pact: Divine

The classes that get access to each skill are:

Recruit: Cleric, Knight, Paladin, Princess, Ranger, Songstress, Princess
Coax: Buccaneer, Patriarch/Matriarch, Wizard
Subdue: Beast Tamer
Tame: Beast Tamer
Control Golems: Warlock/Witch, Wicce
Master Undead: Necromancer
Demon's Pact: Lich
Fey Pact: Rogue, Shaman, Vartan
Seraph's Pact: Cleric, Divine Knight, Priest, Princess

Every unit has a loyalty (which changes based on various things). You can check a unit's general loyalty by bringing up the help option and highlighting their name. It will give you a line, which will show what their loyalty range is, based on alignment. The lower a unit's loyalty, the easier they are to recruit.

(The following info is taken from a reference post on the GameFAQs board for the PSP version)

100-81
Lawful: This unit supports you in all things---a loyal ally to the end.
Neutral: This unit backs your every decision.
Chaotic: In the eyes of this unit, you are a worthy leader who can do no wrong.
Creature: This beast purrs like a kitten when you draw near.

80-61
Lawful: This unit often speaks on your behalf to win others to your side.
Neutral: This unit looks favourably on your decisions and shares an understanding with you.
Chaotic: This unit is prepared to put aside its own interests in service of your cause.
Creature: The beast has taken to you, a loyal companion that will fight at your side.

60-41
Lawful: More often that not, this unit speaks in support of your decisions.
Neutral: Though not openly discontent, this unit will not speak against those who are.
Chaotic: Though not openly discontent, this unit makes no effort to keep counsel with you.
Creature: Though still wary of you, this beast is content enough so long as it's fed.

40-31
Lawful: Though not openly discontent, this unit is often at odds with your decisions.
Neutral: This unit averts its eyes when spoken to and often refuses to reply to even simple questions.
Chaotic: This unit often speaks openly of its distaste for your decisions.
Creature: This beast cowers at your approach.

30-21
Lawful: Of late, this unit has grown more vocal in criticising your decisions.
Neutral: This unit regards you with eyes cold and distant.
Chaotic: This unit does not open its mouth but to complain.
Creature: Same as above.

20-11
Lawful: Its not uncommon to find this unit defying you openly in front of others.
Neutral: Often you've noticed this unit staring at you with thinly veiled hatred.
Chaotic: Not only does this unit disagree with your decisions, it seems to openly revile you.
Creature: This beast crouches as though it might spring on you at any moment.

10-0
Warning: At this point the unit is fed up, and sending it into battle may randomly cause your unit to desert your army PERMANENTLY.
Lawful: This unit has lost all faith in you and can scarce look you in the eyes while talking.
Neutral: This unit regards you with violence in its eyes.
Chaotic: This unit regards you with violence in its eyes.
Creature: Same as above.