Relationship between avrdude's "programmer" and bootloaders
If you are using the bootloader, you are not using a programmer. The programmer, when used, is connected to the ICSP pins on the Arduino. The bootloader however expects a well-defined sequence of data from the Arduino through the serial port immediately after reset. The bootloader recognizes that (if received) and reprograms the flash.

If you turn on verbose mode for uploading you will see the programmer type:

-carduino


That is, the Arduino is using the bootloader programming method.

See my post here: What happens when code is uploaded using the bootloader?




  Furthermore, the Arduino IDE lets me choose "Upload" and "Upload Using Programmer" (the first works for me, the second doesn't).


Yes, with "Upload Using Programmer" you need a programmer, such as the AVRISP which you would plug into your USB port, and then select that as the type of programmer to use. In this case, your Arduino does not need to be plugged into the USB as the serial port is not used for programming.

Note that some programmers supply Vcc (ie. +5V) to the Arduino and some don't. The AVRISP doesn't.




  Furthermore, it seems that that "Optiboot" is a different bootloader than the standard included in the Arduino.


As far as I know, recent Arduino Unos (and probably others) ship with Optiboot. Its main advantage is that it is smaller (only 512 bytes).


  More in general, do avrdude need to know the particular bootloader?


I think the smaller boards use STK500 protocol (see links below) and the larger ones (eg. the Mega) use STK500 Version 2. That is because they have a larger address space. So yes, it needs to know the protocol.

When I switched my board type to Mega2560 the "-c" option changed to:

-cwiring


I am guessing from that, the "arduino" is code for "STK500" and "wiring" is code for "STK500 V2".

Protocols


AVR061: STK500 Communication Protocol
AVR068: STK500 Communication Protocol version 2