You will get a level when doing a certain discussion with a certain person. You can check on the wiki, but for example, you can get to level 1 after learning magic from Zorro after having fought the drunk wolf, and level 2 after learning magic after 3 wins against the horse or the rat in the western district. Xav can do it too, but don't remember who else.