Basically, you can start learning them as soon as you have enough AP. Some deathblows may require you to be at a higher level, but you can still get them up to 100% so you'll learn it right when you reach that level. Basically, all the deathblows end with an X attack (3 AP), so you can pretty much figure out what deathblows are available for a certain amount of AP.

For example, at the very beginning when you only have 3 AP, you can't learn any deathblows, because a single X attack takes all you AP. When you have 4 AP, only one deathblow is available (T+X), and when you have 5 AP, you can learn two (T+T+X and S+X).

So the quickest way to learn deathblows is to use a deathblow's particular button combination is combat. Of course, you won't actually perform the deathblow, but your percent learned will increase.