I've managed to unlock 2 classes so far, Gladiator (Battle Master) and Armamentalist (Magic Knight). You get 2 quests in alltrades abby once you can change classes. For gladiator you need to get to super high (100) tension then use dragon slash to kill a slime, you need to do this 3 times and to get 100 tension you need the 16 point monk skill. For magic knight you need to use wizard ward, then the person who used ward has to get the killing blow on a metal slime, this needs to be done twice. While your working on the battle master quest you might as well pick up another quest (also found in alltrades abby). The quest asks you to get to super high (100) tension 5 times, that is it. Once you do this quest you are asked to come back once you have an entertainer at lv 40+ for another quest I would assume. I believe this is part of a chain to later unlock the superstar (don't know it's real name) class.
I just made my warrior into a gladiator, now to start grinding again lol.
Edit: There is another quest you can get in alltrades abby, get a lv 15+ mage to sleep at the inn at the abby and you will get a quest. Once you do that quest they tell you to come back once you have a lv 40+ mage, I'm not sure but that may lead to unlocking the sage class.
Edit 2: Just unlocked paladin, when you get to Gleeba (next place after you get the boat) there's a paladin in the palace that gives you a quest to use whipping boy to take 10 attacks for a party member. I found it easy to do just outside gleeba, there's a monster that has a group breath attack. Not sure on the lv requirement for this, might just be 15+ warrior, my warrior (was a lv 20 gladiator when I found and did this quest) was lv 28 at the time.
I don't think that thief quest unlocks any classes and I could be wrong about some of the above unlocking other classes. I found the quest to unlock ranger in the north end of the lonely plains (1 map east of bloomingdale) Requires you to envenom 3 monsters and let the poison kill them.
You have to do quests to obtain the ability to learn the different classes. You can get the Gladiator quest at Alltrades Abbey and the Ranger class quest is not much further into the game, when you go to seek out Mason at Zere Rocks, there is a guy in front of the cave to the right wearing green clothing who gives it to you (there is a little boy opposite him). I believe there might be a job class for a mage that you get from the faeries when you sleep at the Inn back in Alltrades Abbey, they give you a staff you have to equip to your mage and must kill a certain number of monsters with the Frizz ability. The Ranger one requires you to obtain a certain type of weapon that poisons enemies and poison a few enemies in the cave just before you reach Zere Rocks where the boss is.
Gladiator - Abbey - kill slimes with dragon slash while in a state of hypertension
Armamentalist - Abbey - kill metal slimes with a character that has magic barrier
Ranger - Zere Rocks - kill chimeras with poison
Paladin - Gleeba - use whipping boy 10x
Sage - Gittingham Palace - kill great trolls with Frizz
I believe you have to beat the game or something to get the Superstar class.