I did some pixel art about 10 or 11 years ago, and eventually got a job doing it. Best advice I can give you is to study some sprite rips, and adhere to certain rules. Old school sprites were restricted by the hardware they ran on, which resulted in restrictions such as 16 palettized colors (15 colors + transparent color), 16 x 16 pixels, etc.
NES, I believe, had 4 colors per part, 3 colors + 1 transparent color, which was often worked into the sprite but allowed background elements to show through. Sometimes a character would walk across a background full of stars and you'd see those stars on areas of the character that should have been outlines. Some characters or sprites appeared to have more than 3 or 4 colors, but this may have been achieved by layering more than 1 sprite.
Genesis and SNES (among others), had 15 colors + 1 transparent. SNES also had the benefit of different transparency modes. I can't remember too well, but I think the Genesis had a 64 color limit on the entire screen, while the SNES had 256 or something like that. GBA was similar to the SNES, though they had different transparency modes.
Tile sizes that made up sprites were restricted to powers of 2 in either dimension. 2, 4, 8, 16, 32, 64, etc. You could have a tile size 8 x 32, or 16x16, and a bunch of them stacked to give the illusion that a sprite is more than 16 colors, or larger than 64 x 64. 4 or 8 may have been the minimum size, though. A programmer could probably answer this one better.
I haven't used any modern 2D game engines, but my guess is they support some kind of basic, widely-available image format that allows a transparent color or alpha channel. Those include GIF, PNG, and probably others, so most any image editor should be able to create these. You'll want a more sophisticated tool than MS Paint to make these, though.
If you look past those restrictions, in general you should create your sprites with a specific amount of colors (the lower you go, the more retro it tends to look), and try not to use more than 256 colors over the entire screen. Separate the colors with visible gradients or dot patterns. Antialias by hand, using any leftover color slots first, then with colors that already exist in the palette for the sprite. Don't antialias the edges; they should be sharp with visible pixels.
Drawing the sprites themselves is like any art form: you develop your own style. Personally I like to go one of two routes to start them. I'll either start off with a rough sketch or pencil test of animated frames, scale them to size, and trace over them on another layer with black pixels, or start drawing the sprite from scratch, drawing with black pixels instead of tracing. That consumes 2 colors either way, black and transparent, but the tracing method is best with a program that can handle layers (photoshop, gimp, paint.net). In Photoshop, drawing should be done with the pencil tool at 100% opacity. This way there is no danger of drawing transparent or slightly off-color pixels. Other programs operate in similar ways.
Next, I fill the sprite with white or some base color that I can separate the background or transparent areas from opaque areas. From there I start filling out the character with colors and keep a swatch of that color on the canvas somewhere. Then I create darker versions of those colors and keep swatches of those, then use those colors to add depth to the sprite. If there's space in the palette (or you don't mind working outside a certain number of colors) you can start adding lighter or darker colors. If I don't want the black 'outline', I draw over those. From there it's just tweaking the art and adjusting the colors. Animation can be done on separate layers, or on a different frame if the program supports it.
Now the nice thing about palettized colors is that you can adjust the colors very easily. Just select all the pixels of a specific color using the magic wand selection tool, then adjust the colors as you see fit. If you did it properly, you'll also adjust the swatch you made at the same time. This is essentially how palette swaps work.
That's about all I can think of on the subject... I could go on and on, talk about tiling background tiles, etc., but alas, there is no time. Hopefully the above points you in a good general direction though.
