Before we move forward, one word of advice: usually your theme will give you some sort of recommendations regarding the optimal image sizes. You should pay attention to these recommendations, otherwise your header image will be resized automatically.

After uploading two header images, this is what I can see in the customizer menu:

In other words, the first uploaded image automatically becomes the active header and a "Randomize uploaded headers" will appear.

Just activate the randomizer button and click the "Publish" button to save your changes.

And you're done!

If I visit my site I'll see this ...

... and if I hit the F5 key to reload the page, I'll get this:

Simple as that!