Actually, I think both "random" and "permutation" here are a bit misleading.
"Random" just means "the Fraisse limit of something." This is a very specific notion of randomness, and it may not agree with intuitions coming from probability. The Fraisse limit is a purely model-theoretic construction - given a class of finite structures with nice properties, there is a unique-up-to-isomorphism countable homogeneous structure with precisely (up to isomorphism) those finite structures as its finite substructures - and so there's nothing probabilistic here; the term "random" just comes from the intuition that in Fraisse limits "anything that can happen, will" (which can be made precise by talking about genericity; see my question "Fraïssé limits" without amalgamation). Now in practice, I suspect that there is quite a bit of overlap between the model-theoretic and probabilistic notions of randomness; but I'm also quite sure that they can diverge wildly in more complicated settings.
"Permutation" here is an even weirder term. The random permutation is defined as the Fraisse limit of the "class of finite permutations," where we think of a finite permutation as a pair of linear orderings on the same finite set (the idea being that they define a permutation: send the first$_0$ element to the first$_1$ element, the second$_0$ element to the second$_1$ element, etc.). The Fraisse limit of this class, however, is not a permutation in any obvious sense! Instead, it's a pair of linear orders on a countable set, each of which yields a copy of $(\mathbb{Q}, <)$, which interact 'randomly.'
The tension here is made clear in the second half of paragraph 1.1:
Both linear orders of the random permutation are isomorphic to the order of the rational numbers, and the random permutation is the result that appears with probability one in the natural random process that constructs both orders independently. From this it becomes clear that the random permutation cannot correspond to a single bijection on its domain $D$: indeed, it represents a double coset $Aut(D; <_2) \circ \pi \circ Aut(D; <_1)$ in the full symmetric group $Sym(D)$ on D, where π is any isomorphism from $(D;<_1)$ to $(D;<_2)$, and $Aut(D; <_i)$ denotes the automorphism group of $(D; <i)$, for $i = 1, 2$.
That is:
the random permutation is necessarily not a permutation in any sense,
the random permutation does have a probabilistic interpretation, and
to the extent to which the random permutation has a probabilistic interpretation, it has much more to do with linear orders than permutations.
In particular, there's an intuitive meaning of a 'random permutation' on an infinite set, and this isn't it.
Note that the crux of all this is how we choose to represent finite permutations.
Regarding your other question, on whether Fraisse limits can be thought of categorially: see this post at the $n$-category cafe: http://golem.ph.utexas.edu/category/2009/11/fraisse_limits.html. The answer seems to be "yes, with work," and the post cites Olivia Caramello, Victor Irwin, and Wieslaw Kubis in particular.
