Yes, wine should be de-gassed before bottling. Dry red wines, in particular, should be completely still to ensure they taste right. Dry white wines can be bottled with a little residual CO2; this helps to brighten them up, and fits with the crisp acidity expected.
The good news is that the CO2 will off-gas naturally with time in bulk storage. The bad news is that it requires quite a lot of time - a year or more. For dry red wines made from grapes, this is OK because you should be bulk aging the wine this long anyways. For white wine made from grapes or fresh juice, you probably want to bottle it after 9 months or so, and you may find that it's still too gassy at this point. For wine made from kits, you likely want to bottle it after just a couple of months, which means you will have to de-gas.
As for how to de-gas, the stirring wand that Denny posted is a good option, but using it risks oxidation of the wine if you stir to fast. If you create a whirlpool in the wine, you are oxidizing it. A better method of manual de-gassing, I feel, is to use a brake bleeder vacuum pump - something like the Mityvac.

Edit: I forgot to mention: you just connect the vacuum pump up to a carboy cap and pump away. When the carboy holds about 20" of pressure on the meter for 10 minutes, you know the wine is degassed. Do not pump much higher than about 22" to avoid the risk of imploding the carboy. Here is a video of wine being degassed with a mityvac.
Edit2: CO2 comes out of solution easier at higher temperatures. When you are going to degas, allow your wine to come up to about 70-75F. Don't go higher, because the temperature will start to affect the wine.