What do they mean when saying that a certain value should be “super-logarithmic”? What do they mean when saying that a certain value should be “super-logarithmic”?

I've found the Wikipedia definition of a “super-logarithm”, but I'm having trouble understanding how a given value can be super-logarithmic (in some security parameter).

As for an example of the use of the terminology, see http://research.microsoft.com/en-us/um/people/yael/publications/2010-Symmetric_Encryption.pdf. It appears right in the abstract.
The term super-logarithmic in the paper you cite has nothing to do with the notion of a super-logarithm in Wikipedia. Rather, the intention is simply a function that is asymptotically larger than the $\log$ function. Formally, $f$ is super-logarithmic if $f(n)=\omega(\log n)$. The formal definition of "little-omega" appears in the Wikipedia entry on big-O notation.