Hierarchical clustering with the consensus matrix as similarity matrix
To address your two questions:

Agglomerative clustering requires a distance metric, but you can compute this from your consensus-similarity matrix. The most basic way, is to do this:
distance_matrix = 1 / similarity matrix
Although, they may explicitly state in the paper what function they use for this transformation.

I think this is just to say that the matrix is symmetric. The x-axis of the heatmap will be n=0,1,2,3,4 and the y-axis of the heatmap will be n=0,1,2,3,4. This is the same procedure as for a correlation matrix. Just keep your matrix as is, and it will keep that order.