One of the challenges with the Gemma is that we wanted to have a built-in USB bootloader, but the ATtiny85 doesn't have built-in USB hardware! There are existing USB bootloaders that can work on the 't85 but they use other companies' USB VID/PIDs. Since it not permitted by the USB developer's group to use others' VID/PIDs we had to adapt one of these existing bootloaders to use our USB ID, but we also wanted to not have to re-compile avrdude or the Arduino IDE since that's such a pain.
So instead, Frank (our awesome engineer with mad USB chops) created a USB bootloader that combines the elegance of V-USB with the well-supported and tested nature of the USBtinyISP. This bootloader looks just like a USBtinyISP - and since it uses the unique Adafruit VID/PID we own and that we added to avrdude so long ago, it works with only very minimal configuraton tweaks. No need to recompile anything, whew!
Don't forget to plug in the Gemma via a known-good USB cable to start the process. You should see the green power LED lit and the red bootloading LED pulse indicating that the Gemma is ready to start programming. If you've programmed the Gemma since getting it, you can always get it back to the bootloader state by pressing the small onboard reset button.
Check http://learn.adafruit.com/usbtinyisp/avrdude#for-linux for what to add to your udev file.
Before you try to upload code to the Gemma it must be in the Bootloader Mode. That means its listening for a sketch or program to be sent to it
Don't press-and-hold the reset button, be sure to press-and-release!
See the video below for what it looks like to plug it in, have the LED pulse in bootloader mode, time out and then press reset to restart the bootloader. The board shown is a Trinket, which uses the same upload system as Gemma.