Like most things that originated with piracy groups, the term originated as a way to describe hacks in games that didn't sound quite so illegal. (There are many similarities between the history of "trainers" and the history of "demos", for example).
The original trainer patch programs were generally done by the same groups that pirated games and released cracks to bypass their software protection; often the two jobs were done by similar programs. Even today it's not entirely clear if "reverse engineering ban" clauses in EULA's are enforceable or not, and producing a patch that can do what training programs can do almost always involves reverse engineering.
For those reasons, the groups releasing these programs did not want to call them "hacks" or "patches" or "cheats", but wanted to find a term that game them a sense of legitimacy, and largely settled on "trainer".
The idea is that, by turning off normal restrictions such as limited lives, you could do "practice runs" through a game without worrying that you would die and have to start over. If you reached a particularly difficult area of the game, or wanted to try some new strategy, you could active the "trainer" and practice running through that part of the game over and over until you were satisfied that you could do it normally. Thus, the cheats were a way for you to "train yourself" to play the game safely, in the same sense that you might use blunted "training swords" to practice swordfighting safely.