Bueno, encontre una solucion. No se si sea la correcta, pero tras leer varios libros y articulos sobre los templates, llegue a la conclusion de que hay que meter un #include"implementacion.cpp" en la cabecera al igual que añadir unos #ifndefs
Con esto, todo compila y funciona bien:  
 Código PHP:
    #ifndef ARBOL
#define ARBOL
template<typename T>
class Arbol{
    protected:
        Nodo<T> *raiz;
    public:
        Arbol(){raiz=NULL;};
        virtual ~Arbol()=0;
        virtual void Insert(Nodo<T> nod)=0;
        virtual void PreOrder(void)=0;
        virtual void InOrder(void)=0;
        virtual void PosOrder(void)=0;
};
 
template<typename T>
class ArbolEvaluacion : public Arbol<T>{
    protected:
    public:
        ArbolEvaluacion();
        ~ArbolEvaluacion();
        void Insert(Nodo<T> nod);
        void PreOrder(void);
        void InOrder(void);
        void PosOrder(void);
};
#include"arbol.cpp"
#endif
//////////////////////
#include"arbol.h"
template<typename T>
ArbolEvaluacion<T>::ArbolEvaluacion()
{
}
 
template<typename T>
ArbolEvaluacion<T>::~ArbolEvaluacion()
{
}
 
template<typename T>
void ArbolEvaluacion<T>::Insert(Nodo<T> nod)
{
}
 
template<typename T>
void ArbolEvaluacion<T>::PreOrder(void)
{
}
 
template<typename T>
void ArbolEvaluacion<T>::InOrder(void)
{
}
 
template<typename T>
void ArbolEvaluacion<T>::PosOrder(void)
{
} 
    
  A ver si a alguien le llega a servir