Well, picking the best wine to compliment a given cheese -- or vice-versa -- is a bit complex to fix into a stackexchange answer. I recommend Janet Fletcher's book Cheese & Wine if you're really serious about this.
However, picking a wine which goes OK with the cheese is a lot easier. Here's a few tips based on my personal experience throwing wine & cheese parties:
- Robust red wines ( Cabernet, Zinfandel, Syrah ) compliment no cheeses I know of; they swamp the taste of the cheese.
- Fresh, lower-fat cheeses (chevre, ricotta, Nicasio's Foggy Morning) go well with light & sweet white wines, like a riesling or gewurtztraminer.
- Brie goes well with fortified wines, like manzanilla or muscat.
- Most hard aged cheeses ( manchego, cheddar, asiago ) go well with light, acidic reds like a lighter grenache, pinot noir, or tempranillo.
- Blue cheese generally wants a very sweet fortified wine, like a ruby port or late harvest zinfandel.
- Swiss-type cheeses ( emmenthaler, jarlesberg, St. George, etc. ) work well with medium white wines, like sauvignon blanc or unoaked chardonnay.
Really, what you're trying to do is to have some complimentary and some contrasting flavors in the wine as in the cheese. And generally you want to err on the side of milder wines unless the flavor of the cheese is very strong, since it's too easy for the wine to wash out most of the cheese flavor.
The other fun thing to do is pair cheeses up with wines from the same culture. Manchego with sherry and almonds, Roquefort with sancerre and French bread, pecorino sardo with barbera, cheddar with brown ale.
Hope that helps some.