the tools I use, I used to use about 90% mspaint, and 10% photoshop, just for a few hue shifts and colour tweaks, but now its about 60% photoshop, 30% mspaint
a lot of pixel artists kinda despise mspaint, and to be honest I think the only reason they feel that way is because mspaint gives anyone with a PC access to most of the tools you'll need..
But yeah, I'm kinda switching over to photoshop, there are still some things I like better about mspaint, I guess it's best to use both, at least for me.
I work usually with just some concept art down on paper, for Twinsen I just made a few sketches of him in different angles, and just started spriting him using my sketches as a reference.
Sometimes I do scan my sketches though, but usually for stuff like trees, that just feel more natural drawing on paper first, then tracing over on the computer