If you do get underwear, it's important to get wind briefs or boxers. These are designed for the cold and provide extra protection, and are a little warmer overall. Regular coolmax briefs are much lighter than and less warm than regular cotton briefs, so if you're used to running in cotton briefs, you may find the change to lightweight Coolmax to be a very rude shock. The lighter coolmax variety of brief is really only suitable for conditions that are warm enough that you aren't worried about freezing your goods.
One solution adopted by rec.running readers is to wear shorts and pants together. The running shorts can be worn under the pants, so the liner acts as a brief, or they can be worn over (not by me though!). Either way, it's extra protection for the goods, and it's economical (if cumbersome)
I only have a pair of running boxers, so I can't really answer. However, wind boxers from brands like HIND, SportHill or Sugoi are not like loose boxers one buys in the store. They are fitted, well constructed, and provide good support without being overly tight in the wrong place.
Very satisfied with these. I took them out in the low 20s in 20mph wind, with just the ultra-light Travel Pants over them, and felt fine. The Subzero material wicks nicely, much like the Polartec or swift fabrics.
Hind Drylite Wind-Boxer ($30), SportHill Northwind Boxer ($30)
Garbage. Long in the crotch, loose on the waste, tight around the goods. Not a wind-brief either. Get something else.
Hind Drylite Wind-Brief ($27-), Insport Element Wind Brief ($24-) Helly-Hansen LIFA Wind brief($20-). Haven't tried either of the three, but they've got to be better than this. Note: the items I've noted as ``similar'' aren't really all that similar. Windbriefs are substantially different from briefs, more analogous products would be the ``non-wind'' briefs from the same manufacturers. In this context though -- cold weather clothing reviews -- it seems more appropriate to list wind-briefs