I'm trying to cut a hole into a mesh with the Boolean tool, but it just results in a deformed mesh The Boolean tool is exactly what I'm looking for, according to the countless videos and screenshot tutorials showing it working perfectly. However, I can't get it to work. Here are my steps:

Create a circle w/ face
Extrude the lines to give the circle some volume
Move the circle to intersect the mesh, where I want the hole to be
Add the boolean modifier to the mesh
Select the circle as the object, in the modifier
The result is in the screenshot.

No hole, and an ugly deformation in the mesh.
Can anyone help?
There are two things going on here.  Your extruded circle is still visible, so it is hiding the hole. If you go into the outliner and press the eye to hide it, it will disappear leaving your hole.  (You didn't need to extrude a circle, you could have used a cylinder.
Here's an example:

Now I hide the cylinder in the outliner
and the hole is obvious
Be warnedThe cylinder will still show up in a render. You need to also click the 'camera' icon to keep it from being rendered.
The second thing is a lot harder to deal with, but basically by creating the hole, you've given your object &quot;bad&quot; topology.  There are entire courses on how to fix topology so I can't solve your problem in a single example.
One quick thing you can try is selecting your object, setting it to smooth shading, and then in the Normals property select autosmooth.