Un lenguaje al final es poco más que un parser, la forma de la cual guardas el código en memoria y la forma de "ejecutarlo" (que puede ser interpretarlo a mmento, generar bytecode, compilarlo...).

Para las variables, pues bueno. Depende. Una forma fácil sería tener un mapeado clave-valor donde la clave sea el nombre de la variable y el valor sea la información de esta (tipo, valor, y lo que sea).
En caso de un lenguaje estructurado, habría que tener un map en cada contexto (local, global, namespace, clase...) (Dependiendo del lenguaje, desde luego).

En fin, depende totalmente del lenguaje, paradigma que quieras seguir, etc. Un lenguaje ensamblador, por ejemplo, es realmente sencillo. Su parser es prácticamente trivial y su ejecución lo mismo.
Un lenguaje orientado a objetos como Java o C++, pues ya hay que andar con clases, funciones, imports... El parser se complica ya que, por ejemplo, en un ensamblador solo te vas a encontrar en el código unos operadores que tú has definido. Sin embargo, en Java, vas a encontrarte también cosas definidas por el programador, como nombres de clases, funciones...

Así que antes de nada, ¿qué es lo que tienes en mente?

Si realmente vas a ponerte a hacerlo, lo primero es que tengas claro qué va a ser y cómo va a ser xD
Sintaxis y posibilidades.

Pues nada, empieza a ello. Empieza definiendo <exactamente> la sintaxis que tendrá tu lenguaje: Cómo declarar variables, cómo declarar funciones (si se las vas a meter), cómo hacer bucles, condicionales... También, qué tipos de variables tendrá.

En fin, si tienes alguna duda más concreta, puedes preguntar.