Interesting problem! I'm sure that the median number of rolls to observe all 6 values has a solution through combinatorics. Consider a simpler problem with a 4-sided die (equilateral triangles on the sides). What is the median number of trials necessary to observe all 4 values?

If we roll the die 4 times, then we have 4*3*2*1 different ways to observe all 4 values out of 4^4 possible rolls. The probability of observing all 4 in 4 rolls is 24/256 which is less than 10%. Thus, we need to keep going.

If we roll the die again, then all of the permutations which resulted in observation of every value in 4 rolls also results in observation of every value in 5 rolls. There are 4*3*2*1*4 such permutations. In addition, we might have observed 3 of the 4 outcomes in the first 4 trials, and observe the final outcome in the 5th trial. This can be observed with repetitions in rolls (1,2), (1,3), (1,4), (2,3), (2,4), (3,4). That is, there are 6 ways that we could observe the 4 outcomes in 5 trials, with the final outcome occurring in the last trial. Note that there are still 4*3*2*1 orders in which we could observe the 4 different outcomes with 6 different combinations of repeated values. So, there are 4*3*2*1*6 permutations which result in observation of all 4 values at the 5-th roll. This is in addition to the 4*3*2*1*4 permutations which produced all 4 values by the 4th roll, with any additional value on the 5th roll. So, with 5 rolls, we have

4*3*2*1*4 + 4*3*2*1*6 = 4*3*2*1*(10) = 240

ways that we could observe all values out of 4^5=1024 possible rolls. The probability of observing all 4 patterns through 5 rolls is, then, just a little under 25%. 5 trials gets us almost to the first quartile.

If we go to 6 rolls, then every success through 4 rolls will be a success after rolls 5 and 6 regardless of what was rolled in the last two trials. This is 4*3*2*1*4*4 ways to achieve success through the first 4 rolls with 2 additional rolls. There are also 4*3*2*1*6*4 ways to achieve success through 5 rolls, with anything allowed on the 6th roll. Alternatively, we could observe one value repeated 3 times, with the other three values observed in the other three trials. Enumerating these possible combinations, we have (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,4), (2,3,5), (2,4,5), (3,4,5). Thus, there are 10 combinations of 3 repeat positions out of 5. We could also have pairs of repeats like the first and second rolls result in the same value and the third and fourth rolls result in another value. Again, enumerating all of the possibilities, we have: (1,2;3,4), (1,2;3,5), (1,2;4,5), (1,3;2,4), (1,3;2,5), (1,3;4,5), (1,4;2,3), (1,4;2,5), (1,4;3,5), (1,5;2,3), (1,5;2,4), (1,5;3,5), (2,3;4,5), (2,4;3,5), (2,5;3,4). There are 15 combinations of two repeated values (5 ways to choose the first pair times 3 ways to choose the second pair) for every one of the 4*3*2*1 orders in which we could observe all possible values. Adding these up, through 6 rolls, we could have

4*3*2*1*4*4 + 4*3*2*1*6*4 + 4*3*2*1*10 + 4*3*2*1*15 = 1560

Through 6 rolls, the probability of observing all 4 values is 1560/4096, about 38%.

Through 7 rolls, we have to consider: 1) observing all outcomes in 4 trials (with 3 extra trials which do not alter the outcome, but produce 4^3 observations for every permutation of the first 4), 2) observing all outcomes in 5 trials (with 2 extra trials), 3) observing all outcomes in 6 trials (with 1 extra trial), 4) observing all outcomes in 7 trials with various repetition patterns. The repetition patterns we could observe are: i) one value repeated 4 times in the first 6 trials, ii) one value repeated 3 times, a second value repeated 2 times, and iii) three values observed in the first 6 trials, all of which are observed twice.

Enumerating all of the different permutations, we have

4*3*2*1*4*4*4 + /** observed in the first 4 trials **/
4*3*2*1*6*4*4 + /** observed in the first 5 trials **/
4*3*2*1*25*4 + /** observed in the first 6 trials **/
4*3*2*1*(15 + /** observed at 7th trial; 1 value observed 4 times **/
60 + /** observed at 7th trial; 1 val observed 3 times **/
15) /** observed at 7th trial; each val observed 2 times **/

This produces 8400 outcomes which result in all 4 values of our 4-sided die being observed out of 4^7=16,384 possible outcomes. At this point, a little more than 51% of the outcomes result in observing all values. Therefore, for our 4-sided die, the median number of rolls necessary to observe all 4 outcomes would be 7 (assuming a fair die with equal probability for all possible outcomes).

Combinatorics will produce an exact answer to the question "What is the median number of trials necessary to observe all outcomes?" However, it is simpler to write a program which returns the result. For our 4-sided die, we can code the following:

data sim;
do i=1 to 100000;
outcome = cat(rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25),
rantbl(12928377,0.25,0.25,0.25,0.25));
success=0;
do trial=4 to 12;
if indexc(substr(outcome,1,trial),'1') &
indexc(substr(outcome,1,trial),'2') &
indexc(substr(outcome,1,trial),'3') &
indexc(substr(outcome,1,trial),'4') then leave;
end;
output;
end;
run;

proc format;
value trials
13 = ">=13";
run;

proc freq data=sim;
tables trial;
format trial trials.;
run;

This produces the following cumulative probabilities:

trial CumProb Combinatorics
4 0.0936 24/256=0.0938
5 0.2333 240/1024=0.2344
6 0.3820 1560/4096=0.3809
7 0.5131 8400/16384=0.5127
... ...

The simulation compares quite favorably with the combinatorics. And simulation is so much easier!