You'll need the image files to edit:
under Brawl Vault, resources, there's a Data Partition at the bottom of the page, that contains Brawl's files
http://forums.kc-mm.com/Gallery/Resources.phpGo to Data Partition (it should link to a folder in Mediafire)
and go to
Data Partition\fighter\mario
and choose the pcs file.
FitMario00 is the original/default coloring.
Open that in Brawlbox, look through for a folder (i think it's named "Textures") and there are image files you can export (right click) edit, then replace (right click in Brawlbox again).
save, then put the file where you normally would.
*if you want to use your texture in SSE or some other features, make sure to Save As your new pcs as a pac file as well.
Hope this helps.
edit:
if you don't have Photoshop, get GIMP; it's a free version a lot like it.
It should be on the Resources page as well.