There are a few threads here on how different people built the $50 robot. It would be well worth your time to look these up and see how they built their Bot. Lots of pictures have been posted.
Some of these bots were built with many alternate materials.
So to help answer some of your questions:
1- What is the velcro for? Holding the battery in place and allow for easy removal?
You can use anything that fits your design. Many a couple of pieces of string with free ends that you then tie together to hold the battery.
2- Wood makes a fair substitute. Its fairly light weight and easy to cut and drill. Re-read the tutorial as they tell you that wood or even cardboard could be used instead of HDPE.
3- What is this resistor for? The LEDs and LDRs? Most likely 330 Ohm resistor would work (do read the other $50 bot threads as this has been discussed).
4- It is recommended to use a 6V battery for the servo power. It doesn't need to be a 200mA-h battery (the pictures in the tutorial shows an 1800mAh battery). These are avaliable for suppliers of RC Car and airplane stuff.
5- The ATmega32 can be used but requires a few changes to the code. This means that the HEX file to program the ATmega won't work. You must use the source code, make a few changes and build. This there info in the tutorial on have to build from the source code. Code changes have been discussed in more than one thread to use the ATmega32 instead of the ATmega8.
Keep reading, ask questions and you'll be able to build this Bot.