Just get to it! All you need is an idea.
Try small and simple at first
Post a WIP thread for help and feedback and a place for you to ask questions.

*cure's pixelart and the noobtorial threads above this post is a must read.

8-bit is not a very precise terms. It originally refers to artwork like videogames from real consoles (NES, MSX) or computers (Commodore 64, ZX spectrum, Amstrad CPC) which used a 8-bit CPU.
Two main constants would be :
- Low resolution : For example the NES displayed 256x240 pixels on a whole TV set.
- Low color count. On most machines, the entire screen had to use no more than 16 different colors, and even those colors had to be picked from a specific palette.

Nowadays the term is applied to everything that's retro-ish in the slightest way.

Unless you're a fan of a very specific retro system, there's no need to study the exact technical restrictions (for example the sprite system of the NES, or the MCOL system of the C64). If you want to try draw retro game graphics, pick a general size (like "I'll draw 16x16 dungeon tiles"), choose a small number of colors, and start drawing.
It's very common to pick a power of two : 8x8 are very small and tricky to use efficiently. 16x16 gives you more breathing space, it's a good size to start learning. 32x32 is becoming a bit large.
64px high is enough for a quite detailed character of a platform shooter. 96px high is enough for a VS fighting game (Street Fighter 2).

The number of pixels in an image tells you how much information is present. For example see this :

If you make a 32x16 image that uses only two different colors, you can display it on this device, one image pixel mapped on each "lamp".
Now if you display the same "Happy new year" 32x16 image directly on a modern LCD, with 1 image pixel mapped on one physical pixel, it's going to look tiny. So it's customary to scale up the image for final display :
- while drawing in Photoshop for example, you control the scaling yourself and zoom in and out when you want. It doesn't modify the image (same number of pixels, same printed result).
- in HTML, it's possible to dynamically resize any image. It's what happens in the forum when click and shift-click images. (Images will look blurry in Chrome, but on all other browsers they'll stay sharp)
- For sharing your images, you can always pre-scale them : In photoshop, choose the option resize/resample, be sure to pick "nearest neighbor" and to choose an image size that's an integer factor: 200%, 300%, 400%... This will ensure that all the pixels will be resized to the same size. This way, you can revert the change by resizing 50%, 25%, 12.5%

The numbers that are called "powers of two" are 1, 2, 4, 8, 16, 32, 64, 128, 256 etc. The name comes from the mathematical definition, http://en.wikipedia.org/wiki/Power_of_two

Edit: I found out in Pixelmator you can just turn on a grid that is 1x1 pixel and snap to grid. So I think this solves my problem above.

Edited by donnaloia - 15 March 2014 at 2:12am

They pick a size in pixels, and generally don't care which real-world screen space it occupies. You can not say 'When this is scaled x4, it fills the screen', as it will only work on one screen resolution.

On the pixeljoint gallery and forum, nobody needs to scale things before posting, because there are +/- buttons on the gallery, and on the forums, clicking/shift-clicking an image scales it up.

You still seem to mix real-life size and pixel size, so I don't know how to answer that.

Follow jal's advice, start small. You were referring to a specific pokemon thread : Why not picking exactly this size ?

Only the illustration part, or the text too ? Text is a big constraint because you'll need a pixel size big enough to fit all the text, using a readable font. As a rule, the smallest font that's still very readable has characters 4x6 pixels, including the spacing.