There are three parts to the sharpening process: (1) Profiling/repairing -- resetting the edge angles, changing shapes, fixing broken tips, taking out chips, etc.; (2) Sharpening -- raising a "wire" and "chasing" it off; and (3) Polishing -- smoothing out the scratches and teeth left from sharpening.
Each of these processes is best accomplished at a higher grit level. That is, you profile and repair with coarse stones, sharpen with medium stones, and polish with fine stones.
Since your first sharpening goal is to repair some badly beat up knives, you'll want at least one coarse stone.
However, once your knives are in good shape you'll almost never go back to the coarse stone, so you want knives which sharpen well.
A little polish is a good thing, however a high polish takes a good bit of skill and doesn't actually do much good in the kitchen. In fact, as a beginner, you're far more likely to dull your knife trying to get a lot of polish on it, then you are to help it.
So... You need something coarse and cheap. I recommend a Norton IB-8. This is a coarse India and a fine India combined in one "oilstone." I also recommend that you NEVER use it with oil. Use it with a little water, then once you can reliably use the stone (it will take you about 20 blades), try it dry. Going back to the stone, the coarse India will profile and repair; the fine India will do some profiling, but is a great stone for beginning the sharpening process.
Then add a decent waterstone of around 1000 grit for most sharpening. Once your knives are in order this will be the stone you go to for sharpening. Finally, you'll want something around 4000 grit to chase the wire (sharpen it off) and get a mild polish. Don't obsess about the particular grit numbers. Close is good enough.
You can get these grits in a combi stone which is a good, money saving idea; excellent for beginners. One of the nice things about combis is that they wear out relatively quickly. By the time you know enough to get serious about stone choice, you'll have used up your beginner's stone. Neat, huh?
There are a few good combination stones out there. Two of the better ones are the King 1k/6k and the Norton 1k/4k. Whichever stone CookingAngry recommended is a good one too. I recommend Norton for its very reliable quality and value. Another good choice is the "water stone kit" at Tools for Working Wood. They carry Nortons and some Kings as well.
When you venture into waterstones, you need to think about flattening. You can either buy a flattener, or flatten on wet/dry sandpaper (80 - 150 grit) mounted on glass. I've always flattened on glass, but a flattener is the smart way to go.
A good "steel," whether steel, ceramic or glass is very helpful in a lot of ways. It helps keep your knives performing at their best until they actually dull through wear (rather than minor deformation -- which the steel repairs); and helps "deburr" (chasing the wire), a vital part of sharpening.
Hope this helps,