Casi todos los sprites del juego (además de la mayoría de tilesets, también), como los de los entrenadores, se encuentran comprimidos con un algoritmo llamado lz77 (en realidad es una versión modificada de este, pero esto ahora da igual). Estas imágenes comprimidas se pueden editar con varios programas, pero los más comunes son unLZ.GBA y NLZ-GBA Advance. El segundo es más nuevo, pero los dos te sirven.
Para sustituir un sprite solo tienes que buscarlo en alguno de estos programas e insertar la imagen nueva en su lugar. Para hacerlo, dicha imagen debe cumplir ciertas condiciones, como estar guardada como un mapa de bits (en formato PNG o BMP) y en modo indexado a 16 colores. Si no sabes como hacer esto, buscando un poco en cualquier sitio (en el foro, la wiki de WaH, google, hasta youtube) puedes encontrar un tutorial detallado.