I think you have the wrong end of the stick here. The Attiny85 is not a chip that comes in different speed versions. The datasheet mentions that it can run at 20 MHz. That doesn't mean you can buy a "20 MHz version". By selecting the appropriate clock option in fuses you can run at 20 MHz (or higher). From the datasheet:
High Frequency PLL Clock
There is an internal PLL that provides nominally 64 MHz clock rate locked to the RC Oscillator for the use of the Peripheral Timer/Counter1 and for the system clock source.
I believe these to be pre-set from the factory for the various clock options - but will it matter when I try to program them with the Arduino software?
That list is weird, it doesn't specifically say they are pre-set to any speed. Personally I would regard that list as meaning that the higher speed ones are manufactured to better tolerances, if indeed it means anything at all.
Maybe when they manufacture them they do a quick test at various speeds, and ones that don't run at 20 MHz are put into a different batch.
The datasheet specifies the default clock settings, it would be weird if Atmel made them with different settings unless you placed a massive order.
As for programming them, by default they don't come with a bootloader, so you would need to use ICSP programming anyway. You would need (in any case) something like the AVRISP device (which connects via USB to your computer, and the other end goes to your chip to be programmed). Or you can make up something like my AVR hex programmer which lets you put a hex file from the IDE onto a MicroSD card, and then use that to program the ATtiny85.
In all of these cases you can change the fuses to do what you want, including the clock options you prefer.
There is a board you can buy which is a pre-made gadget using the code I mention above, where you just press a button and the chip is programmed, which would be helpful if you are doing a lot of them.