Either aluminum oxide or silicon carbide paper will work pretty well on most steels, down to grit sizes just a bit larger than the average size of the vanadium carbides in the steel. When grit sizes start approaching the size of the carbides (2-4µ in S30V, for example), the hardness of the vanadium carbides will limit how effectively the SiC or AlOx can abrade and re-shape them (vanadium carbides are harder than either of them). At such smaller grits, it's usually better to finish/polish with harder abrasives, like diamond or CBN. If you're not planning on producing mirrored or near-mirror finishes on your edges, then it likely won't be much of an issue.
Harder backing for the sandpaper will make all abrasives work more aggressively. So, for high-wear steels, that'll be more of a factor to consider. Softer backing, like leather or mousepads, will limit the ability of the abrasive to grind the harder carbides; edges won't be as crisp when finished. The paper will work much better over glass or hardwood (or a bench stone).
David