Stone - +1 on what Jeff B. posted.
Choseras are great stones, but they are on the soft side, I believe. You might want to think about whether you want a set of stones like the Choseras, or Nubatamas (medium to hard, depending on models), or Shapton Pro/Glass (hard to very hard).
If you do a little digging in the sharpening forum there's lots of info on the merits of the different lines, etc. In a quick nutshell:
Hard stones like the Shaptons require more precision on your part and are less forgiving of sloppy technique, but they dish more slowly and the Shaptons are splash 'n go for quick setup.
Softer stones are preferred by some sharpeners. They typically dish more quickly and you can gouge the stone easily with improper technique since they're soft. They are usually not splash and go. Some require longer soaking times before use.
Medium stones like the Nubatama Ume 1K medium are, well, in the middle
, having a combination of characteristics of hard and soft. They are more forgiving than hard stones, but are less likely to gouge than soft stones. They can be almost splash and go or require minimal soaking before use and they can develop more mud than hard stones. Some dish slowly, some more quickly.
Many people recommend starting on stones in the medium hardness range, but YMMV.
Mark carries a ton of great stones with a wide variety of characteristics. Ask away here and pick the brains of some awesome sharpeners (I'm not one of them - yet (I hope someday)).