Click here for a chart showing what monsters appear with random trainers.
Catching monsters is a tricky business. It requires the use of meats to entice the monsters to join.
The meats (ranked in order of effectiveness) are:
BeefJerkey
PorkChop
Rib
Sirloin
Towards the end of the game, when sirloins are more plentiful, it will be easier to throw a few sirloins at a trainer and pick up powerful monsters from them.
But until then, many tricks have to be used.
One good trick to try is with Ironize. Since this skill turns your party temporarily to iron, you can use this to just throw meats for a few
turns while your enemy's attacks are useless. Then, once the ironize dissipates, you will have a good chance of getting a monster to join.