Probably by accumulating weights together, taking an uniform sample on the total range of those weights, and figuring out on what interval corresponding to a value the sample ended (or doing the same by subtracting weights from a random sample until it is below zero), then performing the same with remaining values and weights for the next sample in the case of RandomSample. Like this, but more efficiently:

ClearAll[randomSample];
randomSample[w0_List -> v0_List, n0_ : default] :=
  With[{n = Min[n0, default] /. default -> Length[w0]},
   Last[Nest[
     Apply[Function[{w, v, l},
       With[{r = Total[w] RandomReal[]},
        LengthWhile[Accumulate[Most[w]], # < r &] + 1 //
         {Delete[w, #], Delete[v, #], Append[l, v[[#]]]} &]]],
     {w0, v0, {}}, n]]];

randomSample[{1, 3, 5} -> {a, b, c}, 2]

(* {c, b} *)

If a value is present multiple times in the input (and zero weights are not involved) it can also be present multiple times in the result from RandomSample.

I'm not entirely certain how to interpret your question, but it should also be noted that - although not obvious as a feature - weights can actually affect the order of items on the result, even when it is a permutation. Consider the following, for instance:

RandomSample[{1, 1000, 1000000, 1000000000} -> {1, 2, 1, 3}]

This almost always results the following:

{3, 1, 2, 1}

Thus tallying in order to avoid manipulating the value and weight lists is unlikely to work as expected.

"Discarding" a value in further selections can mean two things: re-running selection step if the item is already taken, or discarding it from further selection candidates. With very skewed probabilities the first option can be very inefficient, while the second is just (relatively) fine.

Based on run time performance I could imagine something like the following being done per resulting value in C pseudocode:

item_t getone(item_t *values, double *weights, double *weightsum) {
  r = *weightsum * randomreal();
  i = 0;

  while (r > weights[i]) {
    r -= weights[i];
    i++;
  }

  *weightsum -= weights[i];
  weights[i] = 0;

  return values[i];
}

One could even perform in-place compaction for such arrays... but I guess I'm thinking on quite non-Mathematica abstraction level here.

There are certainly plenty of options available here if one really wants to go into optimising certain kinds of workloads. Just that it's pretty obvious from run time observations that the simplest strategy of "repeat if item is marked already used" is not at least always used, because if it would, taking a permutation of a list with trillion-to-one weight distribution would not be effectively instantaneous...

Ah, it may be that I misunderstood something...

RandomSample removes the sampled value from the value list before sampling again. So, RandomSample[{1000, 1} -> {1, 2}, 2] may have 1 only once in a result, and only twice in RandomSample[{999, 1, 1} -> {1, 2, 3}, 3], while with corresponding RandomChoice both are capable and very likely to return only ones.

If RandomSample db directly it is capable of returning each unique value the number of times Tally would indicate...