Oi, that sprite is really blurry. Almost like it got sized up improperly? Anyway:
The easiest way to implement what everyone is saying is to find the tallest of all the images and the widest of your sprites (which from what I could figure for both dimensions was the stationary back sprite at 104px wide and 103px tall.)
This should give you a box of 104x103. Multiply your height by four and your width by three. (of if you're using an art program that let's you grow your canvas by percents, grow your canvas height by 400% and your width by 300%) In the end you'll have a file that's 312x412 pixels. Each sprite must sit in it's section on the grid. And, as you can see with Mogmaster's example there, for want a forward walking sprite, then the left walking, then a right walking, and finally a back sprite.
This is the absolute smallest file size you can use for this sprite.
The grid will look like this:
Any smaller, and you will have the issue you are already having. And if any part of the sprite sticks off this grid, it will show up on other instances of the sprite.
This might not be the optimal size for your sprite - depending on your tile sets it might sit too high or two low and you may have to adjust from there. Of it might make the walking cycle bounce if the frames are meant to line up differently. But, it's the bare minimum. Lining up non standard sprites can be a real pain in the butt, so you'll have to play to figure out what your exact widths and heights are. Because I suspect the sideways walking sprite is not the sort that lines up dead centre in the box.
Hopefully that made sense on how things work from a graphical editing standpoint though.