They're esentially a hard abrasive that wear away the knife edge to make it sharp. There are natural and man made "stones" that do this job. They are called whetstones as the word whet is an old verb for sharpening, but also for excitement, derire as in whet your appetite; both could be construed as being brought to a culminating point.
You can spend a lot of money, but you don't need to.
First, read the sharpening FAQ. It's long and will cover terrain that is only tertiarily germane but it all comes in to play in the act of sharpening.
Stones come in different grits/hardness. Soft stones are usually more abrasive than hard. They cut faster to work a dull edge quickly. But they produce a coarse toothy agressive edge. Which is fine for kitchen work. it will also shave arm hair. There are more discerning tests than shaving.... Harder stones produce a finer more polished edge. Japanese waterstones (very expensive) can have infinitesimal grits that produce polished mirror edges.
The old time stone is known an Arkansas stone after a famous quarry there. These can be very expensive as they are a natural product and carefully worked to produce flat regular blocks.
Man made stones include very coarse compressed and bonded carborundum blocks and also ceramic stones and rods or aluminum oxide. And even diamond dust bonded to plastic and metal slabs. I have some of all of them. They all have their uses.
As far as a specific tool, I think the Tri-Angle Sharpmaker by Spyderco is the easiest to use to produce a hair splitting edge. You can cut the type off of a printed page with a knife sharpened on this tool. All you have to be able to do is hold a knife blade straight up and down. If you want, you can also use the system as in the free-hand stone method too. The Sharpmaker runs about $50.00 www.knifeworks.com
usually has one of the better prices and shipping prices.