GBA graphics.... compression can be used and there are worse options than unlzgba for dealing with graphics and GBA compression though it is probably the lesser when compared to NLZ-GBA Advance and Lz77Restructor 2. Also pokemon is actually quite a hard game to hack if you are going from ground up, it has loads of tools though so use those if you especially want to hack pokemon.
I like tiled2002http://home.arcor.de/minako.aino/TilEd2002/
When you say funny looking do you mean the colours are not there or that the graphics are corrupt in some way (errant pixels, deteriorating as things go on....)? If the former then we probably have to discuss palettes- typically console games are not full colour pictures but numbers lining up with an appropriate colour scheme (aka a palette). These palettes can come in many forms and are used for certain types of animation too and are also why you face enemies later in games that look like older ones but with a new jacket.
You can find the palette in the game (difficulty varies from trivial to near impossible to get anything useful) or you can snatch it from the game ram (far easier though you can not edit the colours themselves if you do that and you will need to be in a position in the game where the artwork in question in the colours you want is being used).
XVI32 is on my list of nice freeware hex editors only by virtue of its scripting language, without it I would not really have it and most of its features are tied to it rather than a nice GUI. mirkes.de tiny hexer ( http://www.softpedia.com/get/Others/Miscellaneous/tiny-hexer.shtml
) and http://hexplorer.sourceforge.net/
(you will need to fiddle with the GUI as the stock one is not set up for greatness) are my main two general purpose freeware hex editors though (hex workshop and 010 editor if you go paid and sticking with free I would not say no to a copy of HxD though the others mentioned have more functionality).
Generally speaking though a hex editor is not that useful a tool for actually doing a hack- you are probably going to want to split your time between a tile editor (already taken care of) and a debuggerhttp://www.romhacking.net/documents/361/
Do note you do also have simpler options like http://www.romhacking.net/documents/331/
which works for some graphics as well.
*the tiled2002 program can read VBA savestates if you do not want to hunt down a palette.Change the story, level maps and permissions
I could rattle off hundreds of ways the game developers could have coded it and each changes how you approach things slightly.
Story (assuming you do not just mean text) is not necessarily anything close to what you might recognise as a human readable sequence and is rather a sequence of programming that kicks in when you leave a screen/level (for an analogy think if you tried to read a choose your own adventure from start to finish like a normal book- such a setup is often quite useful for games and both makes the would be hacker's life easier and harder). Nothing stopping you from making soft touch type changes though and following the same broad sequence of events (say still have permanent death at the end level 5 but make it a temporary character) but with entirely different text so the player does not necessarily notice.
Level maps and world maps might be coded differently but it does not really matter as the same logic underpins all levels on every game on every console really.
Permissions... I have yet to read up on the game but assuming we are dealing with rules/laws like others that can vary a bit. Are you looking to change the game and say add a lava tile where there might not be one or just change permissions like can not move over water. The latter might be harder (or might not if you are willing to break things somewhere else) but again you could go the soft touch route and change a level to still effectively block you or not as the case may be using the existing setup, couple it with a light graphics hack as well if you want (going back to water if you can afford to lose it and change the colours to red and you have the lava tile).