Hello there. Hand-painted graphics are indeed very, very classy.
Resolution-wise you never really have to work with a bigger resolution than what the end result is, though it's often good ( and highly recommended ) to work at twice the size just in case.
A good way to approach hand-painted graphics is to try to think about how to compartmentalize a painting into tiles or shapes (think layers in photoshop). An understanding of how to texture 3d-objects is also helpful.
The best way to go about it, I think, is to first paint a mockup and not think about the technical stuff. Then, when you've done that you can start thinking about how to split things up and experiment.
I recently did some freelance work for Oxeye, an awesome company who's working on a hand-painted action platformer called cobalt. They wanted a desert environment and I was initally tasked with doing some mockups - but since their levels usually are in more urban areas they had no sand dunes and hadn't really used that kind of ground tile before. The logical thing would be to treat each dune as a tile and make variations of it to not make it look boring.
This is NOT one of the fancy mockups, it's just a R&D-test to show what kind of technique I used for the tile.
All the dunes in that image are made from one single tile, though resized and rotated. An important thing to note is that the layer with collisions have some stronger tones painted on them to show where the player can and can't stand (they're not tiles, but could easily be turned into some).
The very first thing you should do though, is to get your hands on aquaria and cobalt since they both have level editors equipped for this kind of thing. Study maps others have made in these games and check what tiles were actually used to create them.
This is another R&D-thing I did for a personal (non)-project:
You'll notice it is very inspired/derived from the way Aquaria handles cliffs.
As far as painting skills goes there are a lot of places and a lot of tutorials out there, but it's kind of hard to link to since what we're talking about is essentially being good at painting in general.
http://androidarts.com/art_tut.htm <<<<< That one is really good though, and covers a lot of topics.