@Daniel Thank you very much. But you are slower by a factor of two than my simpleminded solution.

@Rohit: Thank you as well. But you erroneously give containsQ[{a,b,c,b},{b}] -> False

My Solution and test:

test1Q[a_, {}] := True
test1Q[a_, b_] := And[
  MemberQ[a, First[b]], 
  test1Q[
   DeleteCases[a, First[b], Infinity, 1], 
   Rest[b]
   ]
  ]

test2Q[a_, b_] := ContainsAll[Tally[a], Tally[b]]

test3Q[l1_List, l2_List] := 
 Module[{sl1 = Sort[l1], sl2 = Sort[l2], pat}, 
  pat = Riffle[ConstantArray[BlankNullSequence[], Length[sl2] + 1], 
    sl2];
  MatchQ[sl1, pat]]

runWithPredicate[test_] :=
     {
      string = "ZieglersGiantBar";
      letters = Characters[ToLowerCase[string]];
      words = WordList["KnownWords", IncludeInflections -> True];
      set = Timing[
        Select[words, test[letters, Characters[ToLowerCase[#]]] &]
        ];
      First[set],
      Length[words],
      Length[set[[2]]]
      }

     runWithPredicate[test1Q]

    {1.51693, 135364, 2698}

    runWithPredicate[test2Q]

    Out[111]= {3.43823, 135364, 187}

    runWithPredicate[test3Q]

    Out[110]= {3.15315, 135364, 2698}

What really makes me wonder, is that my simpleminded, straightforward recursive approach outperforms your solutions by a factor of two.

I offer a virtual beer for anyone who can do significantly better...

And I like to know what 2000 other words Knuth came up with: Cf. https://en.wikipedia.org/wiki/Donald_Knuth Section Early Life

I'm sure this is not optimal, but one might sort both and try matching the first to a pattern that alternates blank null sequences with the second.

testQ[l1_List, l2_List] :=
 Module[
  {sl1 = Sort[l1], sl2 = Sort[l2], pat},
  pat = Riffle[ConstantArray[BlankNullSequence[], Length[sl2] + 1], 
    sl2];
  MatchQ[sl1, pat]]

testQ[{a, b, c}, {c, b}]
testQ[{a, b, c}, {c, c}]
testQ[{a, b, c, c}, {c, a, c}]

(* Out[1384]= True

Out[1385]= False

Out[1386]= True *)

Perhaps look at ContainsAll?