*Edit, May 2015: Times have changed… again. Schema.org seems the way to go, using either microdata (W3C note) or RDFa (W3C recommendation), where the RDFa Lite variant is easiest to learn. Meanwhile recently Microformats released a new version as well, which nobody is paying attention to currently.
Also see the answer to What is the relationship between RDF, RDFa, Microformats and Microdata?
Edit, August 2011: Times have changed. Forget my recommendation below. Just use microdata and forget that the other two exist.
Microformats: the oldest and the simplest of the three. If the existing specs cover your needs (that is, you want to mark up addresses, events, friend links, or another one of the supported data types), then they are a nice and practical choice. The problem is that you cannot make your own microformat if you want to mark up some kind of data that’s not supported by the official specs.
RDFa: This one is based on W3C’s RDF data model (it’s basically a way of embedding RDF data into HTML pages). RDF has been around for a long time and there’s a large amount of fancy tools for doing stuff with RDF data (stores, search engines, query languages, graph visualizers and so on). So RDFa takes you into this big existing ecosystem. But this also makes RDFa kind of complicated, and the learning curve is steeper than for the other proposals.
Microdata: This is Ian Hickson’s counter-proposal to RDFa. In spirit, it is an extensible version of microformats. It doesn’t have the RDF connection and is simpler than RDFa. It’s still very new and hasn’t seen much adoption yet, so it’s a bit early to tell. Update: schema.org really seals the deal here.
My recommendation would be to go with microformats if they cover your need, and RDFa otherwise.