And what did you use to get that effect, Jad? All I've been using up until now is MSPaint. Downloaded GraphicsGale last night and it's looking to be way complicated...Could I get that effect somehow in Gimp you think?

I'm not sure what Jad uses, but you can just about get that effect in any program.  I use Paint too, but I would suggest GIMP, seeing as its free and still rivals Photoshop.
If you're going to make him crouch down before he kicks or wind up before he punches, keep in mind that a long delay between the time you hit the button and the time the punch is thrown or the kick is kicked shouldn't be too long
Jad's motion streak should definitely be added to your animations, but for the the leg,  I would do two frames of motion streak, the second one having less of a streak so it doesn't disappear too quickly, like on the punch.  Try to experiment! 

Everyone else pretty uch summed up what I had in mind