It's every time you level definitely, but a couple patches ago, you could also wait around in-game for a couple hours and they would refresh. I don't know how many hours (it was four or so at most), or if that is still possible, though.
Maximum AP is generally based on your Constitution. Each point of CON increases your maximum AP by 1. There are also Talents which permanently increase your maximum AP - with a price or catch, Talents which increase your maximum AP under certain conditions (like low HP), and Skills which temporarily boost your maximum AP.
