DS trainers require a nice bit of skill and patience especially as emulation is not up to anything really (3D games especially, nanostray was probably the first 3D intensive game for the DS too), hardware side debugging is available but not so conductive to doing much.
You could get lucky and have a bunch of values and stuff already contained and fairly readable in the rom (DS roms can be broken down into their constituent files which are more often than not given nice names, see ripping and enhancements link in my signature for more on this, some of the files even use plain ASCII for text (this is the only reason I was able to sort out a translation of NSMB)), this is more likely to result in a hacked rom though as you will still have to create a frontend (something I have precisely no idea how to set about).
The other way is to have extensive knowledge of ARM7 and ARM9 ASM, which I am afraid I can not help you with.
2 final things, have a long hard look at the trainers already made and see if you can reverse engineer something from them (the trainered ROMs I have looked at so far are still able to be disassembled via NDSTS and NDSTool while they have the trainers applied, I am sure a fair few people would be grateful if you managed to get the trainer working on another regions release).
It may not give as much of a rockstar buzz when you have done it but there are loads of GBA trainers to look at, loads of decent emulators with great features when it comes to hacking roms and above all there is some documentation in trainer making:
http://www.retrocovers.com/advanscene/html/tool.php
