I'll give you guys a crash course in laser operation here, since there seems to be some interest, but I'll try to be as clear as possible without going into a lot of optical theory about refractive index and electron energy bands.
Basically, all a lens does is change the direction of your light rays. It doesn't change the power, it only affects directionality. You can use lenses to do a lot of different things. If you want a fun way to experiment with this, I recommend the Optics Lab Ray Tracing Software. If you want a free download you might have to look around a bit.
So, let's examine the structure of the laser as outlined on their information page. The first component is a diode. Electrical energy is used to excite electrons to a high energy level and when they drop down, they emit a photon of energy corresponding to the energy gap. Judging from the 808 nm light they give, I'd bet this diode is made of GaAs (Gallium Arsenide, if you're wondering - very toxic btw) or some similar semiconductor. GaAs is a great semiconductor that is an excellent light emitter, but almost always in the infrared. When the light escaped from the diode, it is pointing every which way. The first lens is used to collect this light and make it into a coherent beam. This is then sent to a crystal.
*Terminology* You might often hear physicists talk of 'pumping' a laser. This means supplying energy to it in some form so that it can emit energy in the form of light. So when we were talking about the diode, this was pumped electrically. Crystals cannot be pumped electrically, they need to be pumped with light (photons). This way you can input light of one wavelength and have an output of a different wavelength.
So, there are a couple of crystals used in this laser, and at the end we have our green light produced. However, not all of the infrared light got absorbed along the way. A lot of it travelled right through those two crystals. The danger with infrared is that it can cause you to go blind, but you wouldn't even know it because your eyes can't see it. To get rid of this nasty infrared they have a filter that blocks all of it, but transmits the green light. By now, our nice straight light beam has gotten all messed up from going through all those materials, so another lens is used to straighten it out again.
If you check out the video on the site where it shows the laser burning paper (haha, I just spent so much time watching those videos) you'll notice that the laser is held very close to the paper. The hole it makes is the size of the laser beam at that distance from the output. At farther distances the beam spreads out a bit. Now, judging from the size of that hole, that's pretty small. Realistically, I don't think a lens will be able to focus that beam down too much more. I can't say for sure, but that's just my opinion. It looks pretty close to the minimum spot size.