I would be sad if your top quality video is accompanied by terrible sound. The best microphone depends on your needs, there is no perfect solution.
The internal microphone
The D800 comes with a built-in mono unidirectional microphone. The sounds quality is reasonable and the noise is relatively low. The mono signal is recorded identical to both stereo channels in the recording. Its weakness is the sensitivity to noises causes by the autofocus servo motor, the vibration reduction of the lens and handling the camera. Not only is the microphone very close to the source of the noise, but the noises are also mechanically conducted through the camera body.
External microphones: shoe mount microphones
There are several options for external microphones. Most popular are the microphones that are mounted on the hot shoe of the camera. While this seems a practical place, it still has the downside of being very close to the lens and mechanically connected to the camera. Depending on the model, you will still be able to hear AF/VR/handling noise to some degree. I can help to dampen vibrations with a so-called shock mount or to pick a microphone that is truly directional and not sensitive to the sounds around.
Although these popular microphones are often called shotgun microphones, their sensitivity is far less directional than a real shotgun type microphone. Most of them are super cardoid. Super-cardioid microphones tend to pick up sound coming from exactly behind the microphone too, making them less ideal for indoor dialogue, as they pick up the echo from the speech. To minimize echo, do not hold them in between of the subject and a wall, but use a boom to hang the microphone overhead of the subject at a 45 degree angle pointing at the subject.
External microphones away from the camera
The best place for a microphone is close to and directed at the subject, giving you the best control over the sound.
Handheld microphones (or singing microphones) are intended to pick up only sound from very close to the microphone. For dialogue, they are pretty much useless on a boom so you can't keep them out of the shot.
If you record the audio with the camera, you need a long (extension) cable or a wireless system. Now you can place the microphone(s) wherever you like. If you're using a cable, make sure it hangs loose - if it is stretched tight it will physically conduct the mechanical noise from the camera.
For example, if you're shooting a wedding, you could place a lapel mike on the groom. It is sensitive enough to pick up the minister and vows. This will sound a lot better than recording it from a distance in a reverberant church.
Lavalier type microphones
Lavalier type (or lav or lapel) microphones are small microphones that are easy to conceal or attach to clothing (like a tie, jacket or collar). If you need to bring a microphone close to your subject, these small devices are the least intrusive option. They are omnidirectional so they will not only pick up the voice of your subject but also everything else that is around, even a barking dog next door.
On the internet, the Audio-Technica ATR-3350 seems a popular lavalier type microphone because it's rather cheap. The volume is rather low and the sound quality isn't top notch but it works. The cable is very long which makes it easier to use further away from the camera. Although it needs a battery to operate, it is not amplified.
External sound recorders
If you don't mind some post-production, using an external sound recorder is also an option. This is the way professionals do it. The benefit is that you have full flexibility in your audio recording equipment and you are not tied to the camera. The downside is that it requires synchronizing the video and separately recorded audio track back together in post processing.
Fortunately, there is software to help you with this; doing it all by manually can be time consuming. The D800/D800E does not record a timecode to help you with synchronization, so you will need software that uses the sound from your built-in microphone as a reference point to align the external sound recording.
For an external recorder an old dictaphone, a laptop or even your smartphone can be great to start with. You could use their built-in microphones or plug in an external microphone. For better result you should invest in a dedicated external sound recorder. Popular pocket sized models are the Tascam DR-40 or DR-100, and the Roland R26. Audio brand Zoom offers the cheap H1 and the more expensive H4n, amongst other models. The H4n is one of Zoom's more advanced models and offers a 4 track digital recorder with an on-board stereo microphone plus two separate microphone inputs. With that setup you will have something to choose from in post!
Stereo or mono?
The idea of recording in stereo might appeal more than recording in mono, but hold on.
Recording a true stereo sound image needs two microphones a few feet apart. A mediocre solution are so called stereo microphones that contain two microphone elements, one turned a bit to the left and one a bit to the right. These microphones do not record straight ahead in a directional way. This is not true stereo but usable for ambient sound and music, but not so good for single person speech.
It is likely to give you too much echo and ambient noise for good speech recording. This also goes for the Zoom external recorders that have "stereo" microphones built in.
If you want to record speech from a single person, you will likely want a microphone aimed straight at that person and a mono microphone will give you more satisfying results. For recording a dialogue between two people I would advise two mono microphones for controlled results, but a stereo microphone aimed between them might work for you.
I you plan to record a concert, stereo would be nice, but then I would still advise two mono microphones spaced a few feet apart instead of an all-in-one stereo microphone. Note that rock concerts may be so loud that you may need to lower the output of your microphones using an attenuation adapter plug.
Stereo effects are easier to add in post than stereo defects (an overly reverberant sound) are edited out. You can convert a stereo recording back to mono, but it will still not sound the same as an original mono recording. In professional audio, only mono microphones are used and the sound of multiple mono tracks is carefully crafted into a stereo sound scape afterwards.
Amplified or not?
Most microphones are not amplified and produce only a weak signal. Don't let the name "powered" in the microphone fool you - some microphones need a battery or phantom power to produce sound at all, but that does not mean they are amplified. Examples are the ATR-3350 and the NTG2: they both require batteries to operate but produce a very weak signal.
The D800/D800E comes with a built-in microphone amplifier, but it is not of great quality and introduces a lot of noise (hiss) at higher settings. If possible, use a manual setting for the mic sensitivity on the camera so the noise doesn't go up when your subject stops talking.
Some microphones have built-in amplifiers so they deliver a stronger signal. Whether this is beneficial depends largely on the quality of their built in amplifiers. From an electro technical stand point, it's better to amplify close to the source (a microphone in this case) than to amplify at the end of a long cable. In the latter case, you will also be amplifying all the electronic interference the cable has picked up.
If you have a microphone without amplifier and you would like to avoid the D800's amp noise on a budget, you could either use an external recorder or use a microphone amplifier so you can turn the D800 preamp down. A cheap headphone amplifier (like the $8 FiiO E3) would work. In theory you could even use a laptop for this as most laptops have microphone inputs and headphone outputs. Some laptop sound cards even have a software based noise reduction or voice enhancement function. The downside of most laptops is that they cause a small delay, so the audio will be out of sync and slightly behind. The delay is typically around a quarter of a second but largely depends on the hardware and software used. Especially Windows 7 is known to cause more trouble in this respect.
The best sound quality with the least noise is achieved using a professional audio mixer wilt built in microphone amplifier or a dedicated microphone amplifier. They are somewhat larger and usually require AC input. A semi-professional option is one of Behringer's offering. Their mixers start at $50 and are good enough for speech recording.
If you record video outdoors, you will have experienced wind noise, sounding like someone blowing into the microphone or brushing against it. The easiest solution is to shield the microphone or direct it out of the wind, but sometimes it will not do.
You can greatly reduce wind noise with a special microphone cover. This applies only to the external microphones; the internal mic has no room to put a cover or it. The foam covers that come with some microphones are only somewhat functional. What you really need is a so called microphone wind shield or microphone blimp, also referred to as 'zeppelin', 'mind muff, 'dead cat' or 'dead kitten'.
The hairy surface will create a protective pillow of air around the microphone, effectively diminishing wind noise. Inside the blimp, the microphone is suspended by rubber bands to prevent handling noise.
These dead cats can be bought ready-made but are not too difficult as a DIY project. There is no need to give up one of your household pets, synthetic fur will do just fine.
Or go to the index of all Nikon D800 video questions.
"The camera sees more than the eye, so why not make use of it?" (Edward Weston)