The Völsunga states that Brunhild was a child and raised to be a Valkyrie, implying that Valkyries were mortal maidens. However while there's no indication of whether or not they age, they can go to Hel, as Brunhild does in the Helreið Brynhildar, after her death.
So they aren't immortal (as even the Aesir are not). So it seems likely that they either receive the apples of Idunn, or, they eventually are retired, to be replaced with younger maidens. While they are psychopomps, they are obviously not dead, like the souls they carry to Valhalla (who obviously do not age, since they are no longer alive).