As mentioned previously, paper towels are one of the best substrates, and are the recommended substrate for juvenile leopard geckos (as well as sickly geckos), but can be used for any leopard gecko. With paper towel substrate, there are no worries about ingestion or inhalation of substrate, and it is very absorbent, hygenic, and easy to clean (which reduces the chance of illness). It also makes monitoring health (e.g. eating, bowel movements) easy.
This is where the debate over substrates gets heated. Sand is considered unsafe by some, due to the risk of ingestion and impaction (either due to accidental ingestion or intentional ingestion to meet calcium needs) -- this is a bigger risk for juveniles so sand should never be used with juvenile geckos. Other potential difficulties with sand include dust (which can lead to respiratory problems), and bacterial or mold growth in wet sand. Still, some keepers prefer sand as a substrate.
Healthy adult, properly supplemented, geckos are less likely to ingest sand. If you choose sand, only use it with healthy adult geckos (never juvenile geckos or sick geckos). Choose a fine grained sand. Calcium based sand is claimed to be digestible and thus safer, but it is digested too slowly to be considered a fail-safe option. Provide a dish of calcium supplement to help meet calcium needs. Feeding prey items in a dish can also reduce the chance of ingestion. If sand starts appearing in bowel movements you should stop using sand immediately. Also monitor for signs of obstruction which indicate the need for an urgent visit to a vet: decreased appetite, decrease in bowel movements, lethargy, and dark spots on abdomen.
Like paper towels, paper is utilitarian but safe and easy to clean. You can get brown butcher paper or unprinted newsprint quite economically and just replace the substrate when it is soiled.
Indoor/Outdoor or Reptile Carpet
This is also easy to clean and carries little risk of ingestion (but watch for loose threads that could possibly be ingested or trap a leg), but these can be a bit rough for gecko skin. Keep two pieces on hand to make cleaning easier (when one is soiled, remove it for a thorough cleaning, simply replacing it with the second piece. When the soiled one is disinfected and dry, you can just swap them out again).
Reptile Bedding (Eco-Bedding, Bed-a-Beast, etc.)
There are a variety of bedding products available and some people use these with geckos. Some consist of small particles that could be ingested with feeding, and many experts advise against them. If you choose such a substrate, take the same precautions as with sand.
Dr. Gecko (site no longer available) recommends the use of slate rocks, set into a small amount of sand to anchor them and fill the spaces. If you can get smooth flat stones this seems like a good option for making a naturalistic environment that holds and distributes heat well, without much diminished risks of ingesting substrate (the amount of sand between the stones is less likely to be a problem than an open area of sand).
Substrates to Always Avoid
Wood chips, wood shavings, corn cob, walnut shells, and gravel are not appropriate choices for leopard geckos.