Alaska. With an average annual salary of $43,080, Alaska tops our list of the highest-paying states for CNAs.