All instructions below may refer to the "Nook," but I am speaking about the Nook Color.
Attached to this first post is a PDF file with just the images from these instructions for those folks that just want to cut to the chase.
EDIT: Although my video settings show leaving framerate the "same as source," I would recommend a framerate in the pull-down menu of 29.97 (or less). The Nook Color seems to struggle with 59 to 60 frames per second in the event you have some HDTV video.
Step 1:
The latest release of handbrake can be had here:
http://handbrake.fr/downloads.php
Download and install