The exact difference between a permutation and a substitution I've noticed confusing definitions about permutation and substitution, preventing me from understanding the difference.

A permutation changes the order of distinct elements of a set, but this can be written as a function changing one element by another, exactly as a substitution.

So, how exactly can we distinguish between these two notions?

This question is interesting since we have these two notions in block ciphers, in which S-boxes perform substitution. The problem is that this table is used to replace one element by another, exactly like a permutation.
As noted in this answer and this answer to another question, permutation is just a mathematical term for a function $\sigma:X{\rightarrow}X$ that maps a finite set $X$ onto itself, in such way that for each $y \in X$ there exists exactly one $x \in X$ such that $\sigma(x) = y$. This is also equivalent to how the term substitution is used in cryptography, so your question is indeed justified.

For instance, the term Pseudo Random Permutation denotes a function that might also have been described as a Pseudo Random Substitution (but never is).

As D.W. pointed out in a comment below, the terms P-boxes (permutation boxes) and S-boxes (substitution boxes) have a specific meaning in block cipher design. Suppose you have a P-box and a S-box that both map a bit-string of length $n$ to another bit-string of length $n$. In such case the P-box can be expressed as a function $\sigma:[0..n-1]\rightarrow[0..n-1]$ that maps one index in the bit string to another, while the S-box, simply put, does more. This means that there are only $n! = \Pi_{i=1}^ni$ different P-boxes that map one bit string of length $n$ to another, while there are $2^n!-n!$ different S-boxes that map any bit string of length $n$ to another, without being a P-box and without mapping two different inputs to the same output. 

Using the term Permutation in the specific meaning described in the above paragraph is unambiguous within the field of block cipher design. However, I would recommend using the term P-box, which, to the best of my knowledge, is never used in a meaning that differs from above.

Why? Well, for instance, a block cipher designer who hypothetically decides to incorporate e.g. the RC4 key schedule for setting up the S-boxes used in a block cipher, would be technically correct to refer to the operation that sets up those S-Box as a "permutation" (because one property of such a S-box might be best understood by looking at the setup in terms of permutation decomposition). The result would clearly not be a P-box, though.

Consequently, the best answer is probably that the distinction must be clear from definitions made in the context where the terms appear. When in doubt, avoid terms that might cause confusion.