Art program to create custom sprites?

[Xirix]

I'm very new to spriting and haven't a clue where to start. Any tips and program suggestions on what to draw it in?

I'm not planning on doing anything super-complex, just want to make some custom sprites for a Mario romhack.