All computers have a "machine code". The very first programs are written in machine code.
There is also "assembler" which is a little bit higher abstraction over machine code. You can write anything you want with Assembler.
Above that are simple languages, like Basic or C, which you can also use to write any language you wish.
What is useful these days is the ability to "cross-compile", which is to compile code for a new machine using an existing machine. All you need to do after that is copy the file properly. So, ideally, you could write a new language with whatever language you wish, so long as you have the ability to cross-compile (or something equivalent).
When it comes to actually writing a language, that is a very involved subject. The first languages (FORTRAN, Basic, etc) were very simple because they were written very simply.
After that languages were generally written with a "recursive descent" algorithm, which is very powerful. (You can google it.)
Many languages today are written with a LR parser (or some other form of a lookahead parser). You can read more about types of parsers and get links from Wikipedia:
http://en.wikipedia.org/wiki/Parsing
Hope this helps.