Na verdade Gandalf é um Maia, um ser da mesma ordem dos Valar mas inferior em poder. Os Valar e Maiar não são elfos.
No princípio, antes mesmo do universo existir, surgiram da própria mente de Eru (Deus). Estes seres angelicais que podemos equiparar aos antigos deuses clássicos ou mesmo aos anjos eram denominados Ainur, os Sagrados. Quando o universo foi criado, alguns deles se afeiçoaram à criação e quiseram nela habitar. Os que nela entraram passaram a ser conhecidos como Valar, isto é, os poderes, e que passaram a moldar e reger o mundo em nome de Eru (Deus). Dentre os Valar, como foi dito, haviam os mais poderosos e outros com menos poderes, que foram chamados de Maiar. Gandalf é um deles.
Já os elfos foram criados bem mais tardiamente a partir da vontade de Eru, bem como o foi com os homens. Ambos, elfos e homens, por terem destínos ímpares em relação aos seres angelicais, os quais nada sabiam sobre eles, foram chamados de Filhos de Eru.
Como a Hadriallë Malva já disse com muita propriedade, Gandalf residia em Valinor, a terra abençoada dos seres angelicais os Valar e Maiar, e foi designado por seu superiores a ir à Terra-média para ajudar os povos a lutar contra Sauron. Saruman e Radagast também são Maiar enviados nesta tarefa e. Juntos, chegaram à Terra-média no princípio da Terceira Era, encarnados em corpos de velhos, e foram conhecidos como a ordem dos Istari, isto é, dos Sábios.
Portanto, no final do Senhor dos Anéis, Gandalf na verdade está voltando para casa.
Essa foi uma breve explanação. Para saber mais sobre toda esta história, aconselho você a ler ao Apêndice do Senhor dos Anéis; o Silmarillion, principalmente o primeiro capítulo que trata da criação do mundo, e o segundo, que trata da descrição destes seres; os Contos Inacabados, onde há um capítulo exclusivo que trata dos Istari, isto é, os magos. As Cartas de J. R. R. Tolkien também traz várias informações sobre eles.
Links úteis:
Valar
Istari
Gandalf
Elfos
Espero ter ajudado