Can someone explain, explicitly, how to, given a reductive complex algebraic group construct the Langlands dual group? I know it is a group with the cocharacters of G as its characters, but how does one go about writing down what group it is?

You can construct the dual group in a combinatorial manner as follows: Reductive groups are classified by their root datum. There is an obvious duality on the set of all root data, and the dual group is the reductive group with the dual root datum. You can see Wikipedia for the notion of the root datum. 


The Chevalley construction mentioned by Steven Sam from Lusztig's notes can also be found in Springer's textbook "Linear algebraic groups" (on pages 164165 of the second edition). It's beautiful and clear and elementary (no perverse sheaves!) and direct (no Lie algebras, which wouldn't work in finite characteristic, and no reduction to simply connected groups). If you want to construct representations of the dual group directly, then geometric Satake is a good idea. For the classical Langlands conjectures, what one cares about are not representations of the dual group but elements of it (or a little more precisely, maps of Galois groups into it). For such purposes, the Chevalley construction by generators and relations is just what Dr. Langlands ordered. 


One way to "construct" the Langlands dual group is via the geometric Satake isomorphism, which gives an equivalence between the category of representations of the Langlands dual group and the category of G[[t]]equivariant perverse sheaves on the affine Grassmannian. From the category of representations, the group can be reconstructed via Tannakian duality, i.e., as automorphisms of the fibre functor. I suppose whether or not this is an explicit construction depends on your point of view. 


Lusztig explained how to construct a reductive algebraic group from a given root datum in a class I took from him. I took notes and scanned them. If you don't mind the quality, you can find the construction in Lecture 14 (starting from p.34) here: http://math.mit.edu/~ssam/notes/alggp.djvu The construction is similar to constructing a semisimple Lie algebra from a root system. 


As Peter mentioned, reductive groups are determined by their root data, and the Langlands dual is given by switching weights with coweights, and roots with coroots. There is a "construction" of a group from a root datum in SGA III Exp 25 (in vol 3). It starts by reducing to the simply connected semisimple case (meaning there are ways of going from this case to the general case). The weights give you a torus T, and the positive/negative roots give you unipotent groups U+ and U. You form a scheme \Omega = U x T x U+, and create G by gluing a few disjoint copies of \Omega together, and writing down a composition law. This yields a split group over an arbitrary base scheme. 


Again, I'm always responding to old posts... (do I need to keep mentioning this or is it perfectly acceptable to reply to old questions?). I'm not sure if this is what you mean, but my gut reaction is to use the highest weight theorem and various formulas (e.g. Kostant). You index the irreducible representations by the dominant characters and use the formulas to figure out the dimensions of all the weight spaces and how to write tensor products as direct sums of irreducibles. 


I was googling for the root datum. This site and a very nice, conscise treatment of Calder Daenzer turned up: http://www.math.psu.edu/daenzer/Root_Data_for_Reductive_Groups.pdf His notes deal with complex, reductive groups only (as requested by the OP). In the end, he states the definition of the Langlands dual group. Perhaps, you will also like Casselman: http://www.math.ubc.ca/~gor/Notes.pdf I am aware that this question is pretty old! I add this as answer because I was not quite satisfied with the remaining suggestions in relation of brevity/precision. E.g. Springer's book requires a massive book keeping of notation. I am aware that Springer's/the SGA proof works over any basefield, and is thus more general. 

