If you just call Collection.shuffle on the multidimensional list, it will shuffle the order of the sublists within that list.

If you instead want to shuffle all the sublists, you have to call Collection.shuffle for each sublist.

final List<List<String>> list = Arrays.asList(
        Arrays.asList("A", "B", "C"),
        Arrays.asList("X", "Y", "Z"),
        Arrays.asList("1", "2", "3")

);

// 1. Will shuffle the order of the sub-lists
Collections.shuffle(list);

// 2.a. Will shuffle all the sub-lists
list.forEach(sublist -> Collections.shuffle(sublist));

// 2.b. Or the same, with method reference instead of lambda
list.forEach(Collections::shuffle);

Edit after edited question

If the requirement is really to shuffle all elements of all sublists and even mix elements between sublist, above code will not be sufficient.

The below code will do as you request, but it will assume that all sublists have the same size (in this case 3):

// 1. Add all values in single dimension list    
List<String> allValues = list.stream()
        .flatMap(List::stream)
        .collect(toList());

// 2. Shuffle all those values
Collections.shuffle(allValues);

// 3. Re-create the multidimensional List
List<List<String>> shuffledValues = new ArrayList<>();
for (int i = 0; i < allValues.size(); i = i + 3) {
    shuffledValues.add(allValues.subList(i, i+3));
}

If you want to do a deep shuffle, I would recommend an approach that checks whether each item in the list is another list, and shuffle that list, recursively. Something like this:

public static void deepShuffle(List<?> mutliDimensionList) {
    for (Object item : mutliDimensionList) {
        if (item instanceof List) {
            deepShuffle((List<?>)item);
        }
    }
    Collections.shuffle(mutliDimensionList);
}

You can add multithreading to potentially increase performance with a ForkJoinPool or something similar. That's entirely dependent on your use case though.

Edit This answer no longer applies to the edited question. However it should work when individual sublists need to be shuffled independently.