The chances of evade improving depend on your int and dex. The higher the dex, the more you evade. You don't learn form mistakes, just successes, so low dex/low int races get shafted here. Bad.

My strategy for learning Evade is to master every other skill I can, then hope I get some lucky level gains or Imm XP. Otherwise, I won't waste my time.