Debian squeeze has a package called arduino-core which brings in the necessary bits. avrdude avr-gcc and maybe some other stuffs.
Boot loader might need to tweaked a bit to run at 12 mhz. I should go ask on the arduino forums. I know that they have 16mhz and 8mhz boards available.
I will have to check inTo jtagice mk ii.
Currently trying to find information on 12mhz, the first page of the atmega 8/168/328/etc datasheet mentions that you can do 0-10mhz with 2.7-5.5 volts But I guess thats just chip rating information, not directly specifically connected to "if you're running at 12mhz you need this many volts"
Looks like at 12mhz that is fast enough to do USB 1.1 in software. Project called V-USB for that. I'm not seeing anyone saying you shouldn't do 12mhz with 3.3v
Looks like the arduino bootloader uses the frequency to decide what baud rate to use.
JTAGOCE MKII: I read the docs for it and yes it looks like we're talking about the same thing.
If you are expecting users to put an Arduino boot loader on the 328 you would be better going with an 8MHz resonator that is standard for the Lilypad arduino which works at 8MHz & 3.3V. If you use 12Mhz the boot loader will have to be patched and also there will be work needed on the core files. The arduino timing system is only accurate at 8 or 16Mhz.