cpan1 already gave a guide; here's a little elaboration
1) Download HxD
2) Open ROM in HxD
3) Determine which Pokemon you want to replace. Say you want to replace Cobalion with Groudon.
4) So, in HxD, press Ctrl-F, set Datatype to Hex-Values and search for 78 01 7E 02 2A
5) Groudon's pokedex number is 383, which is 0x17F in hex.
6) Replace 78 01 7E 02 2A with 78 01 7F 01 2A
7) Save changes
8) Run ROM in emulator, encounter groudon.
Now, the sprite won't appear as Groudon, it'll still be Cobalion.
1) Use my Lua script provided here.
2) At the encounter area, find which overworld file is being used.
3) Find the XY coordinate of the Cobalion NPC
4) Open the overworld file and select the NPC data; then using the overworld structure just change the sprite number that the NPC has. You can test various sprite numbers with this script.
5) Put the overworld file back in the overworld narc with PPNFR, then reinsert the narc into the ROM with NitroExplorer
6) Go in game and verify that you did it correctly.
The encounter text will have to be changed with PPTXT.
A general process of adding an NPC is done in
. You're not adding an NPC, you're just editing one; the same process applies here.