Determining which pin triggered a PCINTn interrupt?

I think the naming overlap of vectors and pins is confusing

It is!

The reason there are 8 different external pins for an interrupt vector is to make it easier to layout the PCB or to use a different pin if there is a conflict with another pin function.

Am I correct in thinking ... the only way to determine which pin(s) caused the interrupt is to record their state after each interrupt and compare the previous and current values of all the pins which are enabled in PCMSKn?

Pretty much, lets say you only care about PB0 (PCINT0) and PB1 (PCINT1). So the pin change enable mask PCMSK0 would be set to 0x03.

// External Interrupt Setup
...

volatile u_int8 previousPins = 0; 
volatile u_int8 pins = 0; 

ISR(SIG_PIN_CHANGE0)
{
    previousPins = pins; // Save the previous state so you can tell what changed
    pins = (PINB & 0x03); // set pins to the value of PB0 and PB1
    ...
}

So if pins is 0x01 you know it was PB0... And if you need to know what changed you need to compare it to previousPins, pretty much exactly what you thought.

Keep in mind in some cases, pins may not be accurate if the pin has changes state since the interrupt but before pins = (PINB & 0x03).

Another option would be to use separate interrupt vectors with one pin from each vector so you know which one is changed. Again, this also has some issues, like interrupt priority and once the CPU enters the ISR, the global interrupt enable bit I-bit in SREG will be cleared so that all other interrupts are disabled, although you can set it inside the interrupt if you want, that would be a nested interrupt.

For more information, take a look at Atmel's app note Using External Interrupts for megaAVR Devices.

Update

Here is a complete code example I just found here.

#include <avr/io.h>
#include <stdint.h>            // has to be added to use uint8_t
#include <avr/interrupt.h>    // Needed to use interrupts
volatile uint8_t portbhistory = 0xFF;     // default is high because the pull-up

int main(void)
{
    DDRB &= ~((1 << DDB0) | (1 << DDB1) | (1 << DDB2)); // Clear the PB0, PB1, PB2 pin
    // PB0,PB1,PB2 (PCINT0, PCINT1, PCINT2 pin) are now inputs

    PORTB |= ((1 << PORTB0) | (1 << PORTB1) | (1 << PORTB2)); // turn On the Pull-up
    // PB0, PB1 and PB2 are now inputs with pull-up enabled

    PCICR |= (1 << PCIE0);     // set PCIE0 to enable PCMSK0 scan
    PCMSK0 |= (1 << PCINT0);   // set PCINT0 to trigger an interrupt on state change 

    sei();                     // turn on interrupts

    while(1)
    {
    /*main program loop here */
    }
}

ISR (PCINT0_vect)
{
    uint8_t changedbits;

    changedbits = PINB ^ portbhistory;
    portbhistory = PINB;

    if(changedbits & (1 << PB0))
    {
    /* PCINT0 changed */
    }

    if(changedbits & (1 << PB1))
    {
    /* PCINT1 changed */
    }

    if(changedbits & (1 << PB2))
    {
    /* PCINT2 changed */
    }
}