Three main approaches
1) If the game has a hard difficulty and damage changes then work out what it does and trigger it or a subset of it (you get the increased damage part to work but maybe not the always stone medusa heads or something).
2) Change the damage the enemies do in their stats in the game or change the health/constitution/armour class of the player character somehow -- barring environmental hazards and fixed damage in certain enemies (think cacatuars in final fantasy) if you have half as much health the enemy effectively does twice as much damage. Said stats will also work similarly when you approach weapons to change their stats/abilities (enemies will have atk, def, health, weaknesses and weapons will have atk, health, weapon type, is holy, is dark, is vampiric....). It can be annoying to find the internal stats databases for things as you never quite know how things are stored and you have no terribly easy ins like you have for finding infinite health or something you can change in menus or something. If you have a bestiary or inventory that has stats on screen it will usually be similar to that as nobody wants to do more than convert hex to dec for said bestiary or screen display, and when you do find it in the ROM it will usually be all in a long line (or you will have a long line of atk stats, then a long line of def stats....)
3) The crude and somewhat limited but ultimately effective way using shifts. You will also see a similar approach in experience multipliers as they will also use this. The damage will be calculated upon hit, you then do a logical shift the damage (or experience) and then the result is multiplied by 2,4,8,16.... or halved, quartered, divided by eight... if you shift the other way. The GBA/ARM processor is all about shifting and does it really well so that is nice.
It is limited to those as multiplying by 2 is the binary equivalent of multiplying by 10 in decimal in that you just need to shuffle the "decimal" point. You can do additional maths or make it so randomly it either halves or doubles it and thus changes the average.
In any case you would probably want to start like you were making an infinite health cheat, lose some health and find the value that removed it. From there you will have the results of the damage calculation, work your way back through that (maybe changing armour to try to eliminate that and get the enemies if you are going that way, or changing weapon so you can figure out that if you are doing enemy related stuff).
It is basic tracing really and http://www.romhacking.net/documents/361/
is a rough into to doing it with vba-sdl-h, no$gba has a GUI but the underlying logic is the same (set a break on write, work backwards from there).