How does this non-deterministic algorithm to find if a Hamiltonian path exists work?
There's a couple of bits of information that are key to making this make sense:


Each $p_{i}$ should be a label for a vertex in $G$. Typically $p_{i} \in [1,x]$, but it's not compulsory that you have to label the vertices from 1 to $x$. So the first step is effectively producing a putative list of vertices that could be a path. The rest just checks that it is actually a path (a hence why $(p_{i},p_{i+1})$ could be an edge).
The list is not random. It is selected non-deterministically. This is most definitely not the same as randomly selected. Non-determinism is a special theoretical property where a non-deterministic machine can "guess" a correct answer if it exists, however correct also has a special meaning, in that it selects an answer that will lead to an accepting state if such an answer exists. This may not be the right answer, just one that will make the Turing Machine say Yes - so we still have to check it.


So the algorithm guesses really cleverly a list (in fact an ordering) of all the vertices of the graph, and then checks that it actually makes a Hamiltonian Path from $s$ to $n$.