do they mean that two bits can store 4 different COMBINATIONS of values (ie. 00 01 10 11).
Yes. Each unique "combination" (actually they are permutations) of bits represents a different value.
This is no different to the system of counting you are used to: the decimal system, except instead of each digit having two possible states (0 and 1) they have ten possible states (0, 1, ..., 8, 9). In binary (base 2), two digits can represent four different values (2 ^ 2), and in decimal (base 10), two digits can represent 100 different values (10 ^ 2).