How would I go about writing a Virtual Machine

A few thoughts:

• The older instruction sets will be simpler, so they might be a good place to start.
• Choose a risc architecture: decoding the instruction stream will be much easier.
• Ignore things like interrupts, NMIs, etc.
• There's always a lot of fiddly detail in accurately emulating booting. Instead, pick something very simple like starting execution at address zero, with all registers set to zero.
• Real programs will need things like real hardware emulation as well, so don't do that.
• You might want to extend the instruction set with a few special i/o instructions to read a number, write a character (or even a string), etc, so that you can write simple test programs that actually do very simple i/o.
• Parsing an object file format like elf can be a lot of work all by itself. With tools like objdump, you can probably extract just the text section (ie, the instructions) as binary (at least ascii hex).
• Start by writing a disassembler for whatever instruction set you want to emulate, or at least for the initial subset you'll shoot for. You'll need it for debugging anyway.
• Find out how to get gas (gnu assembler) for your chosen instruction set working so you can produce known good object files and test programs.

Unless you have knowledge of other programming languages, and/or a reasonable understanding of assembler, this is a pretty challenging first C project. Never the less, good luck!