As we increase the ISO sensitivity of our digital sensors, "noise" is inevitable. Noise comes in different flavors, ranging from loud and colorful to the more sublime "film grain". Color (chrominance) noise can be the most annoying as it usually manifests itself as red or blue sprinkles in your image. Luminance noise is more subtle, ranging from grainy to blotchy, depending on the camera.
So is noise evil, and something to be obliterated from our images at all cost? In my opinion, the answer is "yes and no". Certainly, chrominance noise can be extremely distracting, as its presence can disturb the mood and quality of the intended image. Some noise, however, can actually make your images appear to be sharper! Psychologically, when we see grain (which tends to look "sharp") it imparts the message to our brains that the whole image is sharp, too.
In this digital age, many of us are quick to use ISOs much higher than we ever did with film. Those of us who can remember film know that, especially with transparency film, ISO 400 started to have serious grain. The grain characteristics of Tri-X Pan film were actually desirable in an artistic sense, because the grain imparted "feeling" to the image. Now here we are, shooting digital, and we're obsessing that an image is "noisey". Let's take a quick comparison. Below are two images shot with slide (transparency film), scanned at 4000 dpi with a Nikon LS-5000 scanner. Click on each image to see a 1:1 crop.

Pikes Peak and Garden of the Gods, Colorado. Fujichrome Velvia 50.

Steller's Jay, San Jacino Mountains, California. Fujichrome Provia 400F.
While both of these images look acceptable at web size, you can clearly see the film grain in the ISO 400 shot, even without magnification. At 100%, there is visible grain (noise?) even with the ISO 50 film.
So what about noise reduction (NR)? There are several places in your workflow where noise can be mitigated. Your digital camera may have built-in noise reduction parameters that run before your image is saved to your memory card. This is especially true if you use a JPEG workflow, as the camera essentially "processes" your image and saves it to the card. You may or may not have noise reduction options in your camera menus. For example, in the Nikon D2x, you can disable NR in your images at ISO 800 and lower, but there will always be a form of NR (at least in JPEGs) at the Hi-1 and Hi-2 (ISO 1600 and 3200) settings. The other place to perform NR is in your post-processing. There are noise reduction utilities built into many RAW converters, for example, but unless you are using camera-specific software, you might not get the best results. There are also two really good third-party software utilities out there that are specifically designed to remove noise. These utilities, Neat Image and Noise Ninja, allow the user to profile and fine-tune noise profiles for a specific camera at a particular ISO rating. They also allow the user tremendous creativity and control over the amount of NR applied.
So why do we want all this complication? Well, too much NR and your images will look artificial and "plastic". Fine details disappear. This is one reason for shooting RAW instead of JPEG when shooting at higher ISOs. In the RAW workflow, while NR settings may be tacked onto the image, they are only applied later in PP when you are converting the image. Better yet, the NR settings in a RAW file (at least with Nikon NEFs) can be completely disabled, allowing the photographer to choose their own noise reduction method. Deciding which camera has the best high ISO performance can be tricky, as each manufacturer has their own ideas about how in-camera NR should be applied. Apply too much NR in the camera, and the image loses detail. Apply too little, and your images may look too grainy.
I believe that while NR during post-processing adds a little work, it is the only way for me to be happy with my images. If the camera removes "too much" noise, I will have no way to recover the lost details. On the other hand, I can always clean up a "noisy" image if I really need to. One interesting note is that in most cases, noise isn't readily apparent in our images until we're viewing them at or near 100%. At this point, one needs to remember that the 100% view in Photoshop is probably MUCH larger than you'll be printing your image. So don't forget to take into consideration the output size when performing NR. Images downsized for the web probably won't look noisy at all, unless you have a lot of chrominance noise in your image.
I have been shooting the Nikon D2x now since early April. A lot has been said about its noise characteristics, and so I thought I'd chime in with my thoughts based on personal experience. Below ISO 400, I generally don't need any NR whatsoever to get an image that I find pleasing (Note: I don't mean to say "noise free", but what little noise there is really doesn't concern me). Above ISO 400, I can start to see the noise in my images; however, as others before me have mentioned, this noise has a very ethereal "grain-like" appearance as it really only appears in the luminance channel. I do not hesitate to shoot up to ISO 800, especially if I am not underexposing the image. Back in the "lab", I'll apply some NR with Neat Image and I'm usually pretty happy. If I post an ISO 800 image on the web at 800x600 pixels, most people (myself included) can't tell it was a high ISO shot. A few times, I have ventured into the ISO 1600 and 3200 realm. My opinion is that 1600 is usable in a pinch, but at 3200 I need to use NR at levels that tend to obscure edge detail. Such is life. If I wanted an ISO 3200 camera, I'd look elsewhere. Here are some examples of D2x images shot at ISO 800, with and without NR applied. All of these images were converted from RAW (NEF) files with Nikon Capture 4.3.1, imported into Photoshop with NR turned off. Click the image to see a 100% view of the rectangle area.

Los Angeles Dodgers @ Colorado Rockies, September 2, 2005. Denver Colorado. D2x with Nikkor 70-200VR 1/500th @f/2.8, ISO 800, High-speed crop mode.

Same image as above, with Neat Image applied using default NR settings and custom profile.

Neat Image applied using custom settings.
As I think you can tell from these images, web-sized files look less noisey than Provia 400F straight out of the D2x even with no NR applied. With the default NR values in Neat Image, some detail is lost and the image softens when viewed at 100%. I prefer to leave a little "grain" as I find it a reasonable compromise between noise removal and image sharpness.
I made some Neat Image Profiles for the D2x using their profile targets shot at a range of ISOs.
Parameters:
Test images were shot in RAW and then converted using Nikon Capture 4.3.1 with noise reduction OFF. Profiles were then generated in Neat Image v.3.0.2 plug-in for Photoshop.
Right-click here to download the package (ZIP archive).
You can load these profiles in your version of Neat Image and season to taste.