You'll need a good sprite editor.
First you open the rom with a tile editor (Crystaltile2, or if that's not good enough, Tilemolester)
You choose the correct mode depending on system (GBA/SNES/MD/NES/...)
You choose the correct tile dimensions, arrangement alignment (Up/Down/Left/Right alone/+shift/+alt/+ctrl)
You open the rom with an emulator and get the palette from the advanced options, and then put those colors in CT2
You'll have to work with the original colors.
You can draw new stuff instead of the original graphics. Either pixel by pixel with the tile editor, or exporting it to a bmp and editing it in paint/photoshop
If you want new colors, then you need to study how that system stores palettes, then modify it with a hex editor (not difficult, it's even fun to do this)
For example, here are the sprites from MW4. I managed to modify some and then when I ran the game again in an emulator, I saw the changes
Just take extra care to assign the color that would be transparent in-game as something other than black (example: green - or any color not used by the sprite)
