Is there any survey/review on this topic? Does Knuth cover random n-choose-k sampling in his TAOCP texts?
I first looked at The Art of Computer Programming Volume 4A ("Combinatorial Algorithms Part 1"), specifically Section 7.2.1.3 "Generating all combinations" (which comes under Section 7.2.1 "Generating Basic Combinatorial Patterns", itself under 7.2 "Generating All Possibilities"). This is focused on ways to generate all the n-choose-k combinations (so it turns out not to be in that section, though you can, for instance, look up how to generate the $m$th of the $\binom{n}{k}$ combinations), but the very first paragraph says "and we learned in Section 3.4.2 how to choose [combinations] at random".
This Section 3.4.2 "Random Sampling and Shuffling" is in Chapter 3 "Random Numbers", which opens Volume 2 "Seminumerical Algorithms" of TAOCP. It's a short section, and the very first page has an "Algorithm S" (so outside this section it will be referred to as "Algorithm 3.4.2S"), which is the following (rewriting to the notation here):
Set $m$ to $0$ (this denotes the number of items we have selected so far).
For $t$ from $0$ to $n-1$,
With probability $p = (k - m)/(n - t)$ (which is the number of items that still need to be selected, divided by the number of items still available to consider), select the current item $t$ (and thus increment $m$).
If $m$ is now equal to $k$, we are done: terminate.
This may call the random-number generator up to $n$ times, and in fact on average (see Exercise 5 of that section) will call it $(n + 1) k/(k+1)$ times. If we don't know $n$ in advance, we can use the algorithm on the next page (Algorithm 3.4.2R = reservoir sampling), as you mentioned.
But the section also says "Significant improvements to both Algorithms S and R are possible, when $k$/$n$ [in the notation of the question here on StackExchange] is small, if we generate a single random variable to tell us how many records
should be skipped instead of deciding whether or not to skip each record. (See
exercise 8.)", and if you look at exercise 8, it gives the algorithm due to Jeffrey Vitter (incidentally, a PhD student of Knuth), which is more efficient.
Rewriting in current terminology, the algorithm is basically:
Compute the (random) index $X$ of the first item that will be picked.
Pick the $X$th item, then repeat for the remaining subproblem (picking $k-1$ items from $n - X - 1$ items).
The details of how to compute $X$ in constant time (if it's worth it) are in that exercise and its solution, which also makes external references to:
"Precise details are worked out carefully in CACM 27 (1984), 703–718," (Vitter, "Faster methods for random sampling")
"and a practical implementation appears in ACM Trans. Math. Software 13 (1987), 58–67." (Vitter, "An efficient algorithm for sequential random sampling")
"A similar approach speeds up the reservoir method; see ACM Trans. Math. Software 11 (1985), 37–57." (Vitter, "Random sampling with a reservoir")
Anyway, regardless of all this, Knuth himself thinks that the best solution is simply rejection sampling (when $k$ is "reasonably large yet small compared to" $n$). Namely:
We can assume that $k \le n/2$ (otherwise the problem of sampling $k$ items out of $n$ items reduces to that of selecting the $n - k \le n/2$ items that are not in the sample).
Maintain a set $S$ of items we have picked.
While we have generated fewer than $k$ items (i.e. size of $S$ is less than $k$),
Pick one of the $n$ items uniformly at random.
If we had already picked it earlier then do nothing, else add it to the set $S$ of picked items.
That's it. (Note that if we don't ensure $k \le n/2$ we might end up needing to try about $n$ times towards the end; see coupon collector's problem).
The remaining question is how to maintain the set $S$. The answer here by John L. suggests using a boolean array of size $n$, which is great if you can afford it. Else you may still be able to use your language library's standard hash set or equivalent. In Exercise 16 of that section and its solution, Knuth describes a way to do it in (on average) $O(k)$ time (specifically, fewer than $2k$ random numbers generated) using $O(k)$ units of memory (in fact, an array of $2k$ integers), using a data structure he calls an ordered hash table. The solution is described tersely there, but it refers to CACM 29 (1986), 366–367, which is the Programming Pearls column in which Jon Bentley introduced Knuth's "Literate Programming" and has Knuth's 2-page Pascal program for the problem.