Si te refieres a los nombres de los entrenadores, eso se hace con una herramienta llamada Advance Trainer, con la cual puedes además editar sus pokémon, niveles, etc.
Si te refieres a los nombres de los personajes, pues eso se hace cambiando diálogos como bien dice Mew2, y así vas cambiando la historia. Si te refieres al nombre del rival, pues eso se hace reiniciando la partida y eligiendo un nuevo nombre xD