Hi El Capitan,
That is a very simple design that should be easy to reproduce on a protoboard. Time spent up front planning the layout will be worth the effort when you come to building it.
For the resistors, I would use generic metal film and 1/4 or 1/8W will be fine. Carbon film is also an option, but they are not as quiet as metal film and cost the same.
For the caps, polypropylene, mylar and polyester are suitable choices. Just note that some can be physically large in size. Again, generic will be fine, especially to get you started. Save trying out boutique caps for later.
For the opamps, OPA2132, OPA2134, NE5532 or NE5534 are all reasonable choices that will work well and won't break the bank. I would suggest the OPA over the NE, but that is my personal preference, NE is fine too. If you can't find those, even a TL082 from Radio Shack will be fine (make this your last choice, again my preference). You will find opamps all over, DigiKey, Mouser, perhaps even a local electronics shop.
If you want to make this real simple, you can forget about the power supply and use two 9V batteries as shown on Mark's
GWado / CMoy Headphone Amplifier. Simple can be very good.
The RJM page is well documented so give it a good read and feel free to ask for help.
Cheers