Are pseudorandom permutation really permutation in mathematical sense?
Formally, a block cipher is a family of permutations, indexed by the key.  More specifically, let $P$ be the set of all permutations (shufflings of elements as you put it) on the set of $n$ bit strings, i.e. the Symmetric Group $Sym(\{0,1\}^n)$.  The $n$-bit block cipher $B$ is a subset of $P$.  The key specifies which element of the subset $B$ is to be used in the encryption/decryption process.

As CodesInChaos points out in a comment, you are confusing the idea of transposition of the $n$ individual bits of the input with a permutation over the set of $n$-bit strings.  Think of DES as being like a monoalphabetic substitution cipher, except instead of having an alphabet of 26 letters it has an alphabet of all $2^{64}$ 64-bit strings.  More precisely (following the formal definition above), DES is a family of $2^{56}$ different monoalphabetic ciphers, and the 56 bit key specifies which monoalphabetic cipher will be used for encryption/decryption.