I just did this drive (back and forth) last week and I have probably done it 30 times during my life (I have family living in KW). I find it best to take the FL turnpike to avoid traffic as one poster suggested. This will save a ton of time. The traffic was fine, but there can be a few slow points. Definitely watch the speed limit on Big Pine Key, and if you want to see the deer, go to No Name Pub as suggested earlier for a drink. Chances are you'll see deer walking around in one of the yards on your way there. The construction wasn't too bad and lot of the debris and damage from the hurricane seems to have been picked up now.
Enjoy Key West and the culture! It's changed a lot in 20 years, but it's still quirky and different.
I agree with seeing dry tortugas park, and taking a sea plane to do it is amazing (though there is a ferry available).
My Blue Heaven is great for just about any meal, but there will be a wait. Garbo's Grill on Caroline St is fantastic for lunch.
I find Ft Zachery Taylor park to be interesting too. The fort is worth an hour exploring, and there are two beaches. The main one is very rocky, but still popular. There is a much smaller "hidden" beach all the way to the far right corner of the park in front of the fort. The water here is calm and clear, and there's a small patch of white sand. Just be mindful of the ban on glass containers as I personally saw the park rangers ask people to eave that violated this policy.
Key West isn't really known for great beaches, but you can check out Smathers, Higgs and Southernmost as well.