It also depends a bit on the type of stain you are applying, pigment based or dye. The advice you've heard about not using too fine of a grit so there is something for the stain to "bite" into applies primarily to pigment based stains. This is because the grooves created by the sandpaper allow the pigment particles to collect, giving a much darker stain effect. The finer grit you sand with, the finer these grooves are and the less pigment collects. The same thing is true with woods that have very small pores, like maple for instance. There is very little space for the pigment to collect and the stain comes almost completely off when you wipe it, leaving very little color behind. This is much less the case with dye based stains. They are true solutions of molecular size dye particles (rather than comparatively large pigment particles suspended in a solvent and binder) and penetrate into the wood's cellular structure. They will color wood regardless of what grit you use - but you still must sand to a fairly fine grit or the sandpaper grooves will stand out and look really ugly!
All that being said, I generally sand to 220 grit on most everything and usually use dye stains as the first coloring step.
The best advice is to always try your full finishing schedule - sanding, staining, topcoating, etc. - on a scrap of the same wood in your project.
Dave