The bootloader is a small program in the AVR's flash which is never overwritten and runs on powerup. The job of the bootloader is to read program data from the UART and write it to the internal flash. Without a bootloader, the only way to load code is using ISP.
The AVR ATMega8 comes with no code in the flash. Code can be uploaded via the ISP (in-system-programming) pins, using an AVR ISP programmer (or even another Arduino).
For Arduino, the ISP is used only once (at manufacture) - to upload a small bootloader. On powerup, the bootloader runs and communicates with the serial UART (TX + RX pins). Now, Arduino can be programmed via the serial pins using the STK500 protocol.
As the serial pins are (typically) connected to an FTDI USB to serial chip, the Arduino can also be programmed over USB.
UPDATE 2
If the tiny is running a sketch then it must already have a bootloader.
I think there are a lot of factors to be wrong here because the tutorial was written pre arduino 1.0. I think the 1mhz one is a problem and best avoided for now. The tin85 w/ Arduino ISP sounds to be pre-arduino 1.0 and needs to compile correctly.
In a few days I will have some time so if you haven't fixed it by then I hope to give you some info.
First I will take 2 arduinos, one as ISP and one as normal arduino. We need to prove the ISP sketch is working correctly when uploading blink to a 2nd arduino.
Once the ISP is proven with arduino 1.0 we need to see why normal compile of the tiny85 fails. It might be there is an updated tiny85 hardware folder for arduino 1.0 on the web but if not then we can change the tiny85 hardware folder sources to use 1.0 instead (hopefully).
FYI: You mention the arduino.h, in versions earlier than arduino 1.0 the file was called wprogram.h, arduino 1.0 also expects a few other differences. If the tiny85 is including wprogram.h I think it will be a problem to also include arduino.h
IDEA
If you have some time spare why not go onto the arduino.cc and down load version 0023 of the arduino IDE. (All of the older version of arduino are available). Upload the Arduino ISP example to the UNO using 0023 then try the upload to the tiny85 (w/ arduino ISP) for the blink sketch. I would expect 0023 to work exactly like the video, so if it fails you can look to the wiring of the tiny85 for the problem. It it works we will know we need to update the tiny85 hardware folder to arduino 1.0 format
If it works in 0023 then you should follow Deans instructions above for Arduino 1.0.1.
UPDATE
The only way I can find to reproduce the error you see is if I attempt to "Upload using programmer" when the programmer is set to "AVRISP". If I upload the ISP sketch to an arduino and attempt to program an unconnected tinyxx I get different errors.
So sorry if these are time wasting questions but.. are you clicking "Upload" in the arduino ide or "Upload using programmer"? You should be clicking "Upload" after selecting the ATTiny (w/ Arduino ISP) as the board.
Info..
It is a bit confusing but the board definition for ATTiny xx (w/ Arduino ISP) forces the correct programmer settings for the normal arduino "Upload". In the arduino ide, the menu item "Upload using programmer" uses whichever programmer is selected on the "Tools>Programmer" menu, in this case probably AVRISP mkII which, if unconnected, will produce the error you have reported.
Best Answer
The Arduino bootloader is a variant of the original STK500 protocol (1.x). The character 't' (ASCII 0x74) is the "Read Page" command. So perhaps it is possible to pull the program out through the serial port via the bootloader using AVRDUDE... But at best I reckon it will take some fancy timing to pull it off.