wherewolfe:
Obviously, there is the issue that the UNO is too big for the hex bug. I've read about etching PCBs, the Arduino Pro Mini, and using the UNO as a programmer or something like that to load it onto an "ISP"? (I'm not too sure how that last one works, any explanation would be much appreciated.) I'm pretty sure I don't have the tools or expertise to etch a PCB, so my options are just buying a Pro Mini, or loading it onto an ISP.
You don't load anything "on" an "ISP". "ISP" stands for "In-circuit Serial Programmer" - it's essentially a device to allow you to program a microcontroller without a bootloader. If you look on an Arduino UNO, you'll see pins labeled "ICSP" - which are what you connect the "ISP" to (yeah - it's a bit confusing; I am not sure why for the programmer they drop the "C", but for the header it is there). In fact, this is how you get a bootloader onto a bare ATMega328 (or other microcontroller); you don't need a bootloader to load the binary the compiler creates; the bootloader is just there so that things are easier (on the Arduino). There is also a sketch you can load onto an Arduino that will allow you to use it as an "ISP" (instead of buying one).
That said - you could just stick with a Nano, with the bootloader on it (though I can't remember off the top of my head whether you need a separate USB to serial cable or other dongle on the Nano to program it).
wherewolfe:
Second, there is my complete lack of knowledge on how the bug itself works. I've learned that it walks using what is known as the "Jamius walking mechanism", but I haven't found any resources about how the mechanism actually works. (Once again, any explanation would be much appreciated.)
Well - there are two motors in the mechanism - one controls the walking of the legs, the other controls the direction the legs "walk".
What you are looking for can be found here, by the inventor:
http://letsmakerobots.com/node/8325
http://jamius.com/
Let me tell you something though - this guy is very smart (and obviously somewhat wealthy). But he also seems to evidence some kind of mental health issues; this is very apparent if you watch his videos. He is likely good with his medications, though - to me it seems like some kind of OCD, or bipolarism, or something of that nature. He seems to have it under control, but at the same time some of those videos seem kinda disturbing to me. I mean, ordinary people don't generally "chuck it all" and then go out, buy a patch of property on a mountainside that you can only get to by hiking, build a "house" out of "junk" (but I have to give props to him actually doing it - that takes a lot of talent and hard work!), which can only be brought in by walking it in, all with the purpose of finishing building a giant sized version of the "walking spider". I really think he'll get it done, he definitely has talent, and drive - but I don't think the drive portion comes from a great place in his mind, unfortunately. He has the mind of a genius artist mad scientist kind of character, and I wish him luck with his projects and ideas; I just hope his self-imposed bohemian out-in-the-woods lifestyle don't lead to a breakdown or anything. And I can't be the only one thinking this, either - he seems to have plenty of friends he spends time with, which is a good thing. I have a friend who at one time acted just like Jamie - tons of energy, then low spots, then tons of energy, etc - he was a mad genius programmer, now he's burned out, living with his mom, and trying to figure out his place in life (and he doesn't seem to get out of the house much, or want in the way of visitors - so not much like Jamie in that regard).