Can the Arduino (specifically, the UNO) be permaloaded to execute a specific set of intstructions every time upon boot?
What do you mean exactly by "permaloaded"?
If you mean "one time programmable" - this isn't really possible (AFAIK, Atmel doesn't have an OTP version of the ATMega). You can however set various protection flags with an appropriate programmer to keep someone from being able to easily read out the hex program or change it. Note I said "easily" - even with those bits set, there are ways around this "protection", but for the casual everyday user, it won't be an issue.
If, however, by "permaloaded" you mean just loaded on to the microcontroller (the ATMega), and it will execute every time it is powered on (and you don't care if somebody can access/change the hex code afterward) - then yes, this is how it works by default. The hex code (generated by the compiler) is stored in a flash-based memory area on the processor, and doesn't go away when power is removed.
The only other thing to note is that on a stock Arduino, there is a slight delay for the startup of your code - this is because the built-in bootloader checks to see if an upload is occuring, and if not, jumps to execute the code already in the flash. You can bypass this by writing the hex file generated by the compiler using an ISP programmer, which will also overwrite the bootloader (and give you an extra 2K of flash for program area); then the code will execute immediately (this is how the bootloader is put into place, btw)...