I have done the ride a couple of different ways out of Yellowstone. Yup - you get close to 10,000'. It gets very hot - over 100 most days.
For what it is worth, it is legal to ride the interstate (I-90) from Buffalo to Gillette (at least it was in 2003). Not a fun ride and no services whatsoever. BUT, it is about 70-75 miles instead of 100 miles if you go through Spotted Horse. I rode the non-interstate route and it is long and hot. The only thing Spotted Horse had was an ice machine outside a closed bar (July 4th). With the temp close to 100, I could not believe the ice machine was unlocked, so you know what I did.
The downside to the interstate is the traffic, lack of services, and a lot of road trash. The upside - the shoulder is very wide and there is traffic should you have a problem.
After Gillette. find your way down to Newcastle for the night (and listen to the coal trains going through every 10 minutes). From there, it is pretty straight forward to Mt. Rushmore.