What is best to try is really only up to how comfortable you feel with your own skills. Tons of links to tutorials have been posted to these forums already, just search and browse through them and you'll find some good stuff.
What I would suggest though, is to not fixate on merely learning "pixel art", but learn the concepts that are important to pixel art. Namely, drawing fundamentals, volume and color theory. These apply no matter which style or medium you end up using, so learning that and then moving on to pixel specific techniques like proper AA, avoiding jaggies and proper dithering, will go a long way.
@Beaverlicious - I can argue with you about whether or not vectors give more possibilities or not (my stance is, nor more or less than pixel art) but that's not the topic, so I don't know why you brought it up in the first place.