Traditionally, unbleached linen thread is the preferred material for bookbinding, but unbleached long-staple cotton will do almost as well. The key is that it is a natural fiber comparable in expected lifetime to the paper and the cover material, and that it have very long fibers, giving it great strength. For less traditional projects, carpet thread, strong nylon thread, or even waxed dental floss can also be used.
The thread should be heavy, heavy enough that you might be as likely to call it fine cordage as you are to call it heavy thread! Thread diameters of close to a millimeter (when uncompressed and not under tension) are quite reasonable. The thread should compress to about 1/2 millimeter when successive turns are wrapped tightly around a pencil.
Before you start sewing, it helps (but is not strictly necessary) to wax the thread with beeswax. To do this, clamp the thread against a block of beeswax with your thumb and pull it through with your other hand. The thread will tend to cut a slot in the wax, so keep changing the angle of pull to even out the wear on the wax. Do this two or three times with the full length of thread before you start sewing.