Plastic beads in your choice of color. Mixes can be found in the crafts sections of large stores, and a larger selection of single-color bags is available at craft stores like Michaels. For this project, I ended up using roughly the equivalent of two bags of beads: half a bag of the black ones and one and a half bags of the clear red ones (I ended up having to get an extra bag of the latter).
Large pizza pan (mine is 16" in diameter). It's important for the pan to be large, because it's difficult to introduce a lot of curvature to the lampshade, and you still want it to cover at least most of the height of your light bulb. Especially if you intend to use a CFL bulb. The pan does not absolutely have to be round, but it really needs to be both wide and long.
Large stainless steel bowl. Metal is ideal in this case as it won't be harmed by contact with hot plastic, the plastic won't stick, and you won't chip, crack, or break it. You really don't want to use a plastic bowl for this, but ceramic or glass might work.
Aluminum foil. I didn't have the wider kind and regretted it, as it's difficult to overlap it without leaving gaps between layers for melted plastic to seep into and trap foil inside. Consider getting some for this purpose, if you don't already have any around the house.
A metal jar lid, like from pickles. It's going to help you create a hole in the lampshade. Make sure it's the right size to fit the mounting hardware of your lamp. Mine was a mason-jar style ring.
Non-stick cooking spray. It's optional, but I used some and didn't regret it.