What does it mean that a set of intervals is sorted by the right and left endpoints?
Yes, you are right. The intervals are of the form (left endpoint, right endpoint).
First, consider the following statement:

The intervals are indexed in order of increasing right endpoint

It means that given a set of intervals $I_{1}, \dotsc, I_{n}$, the $(\textrm{right endpoint of }I_{i})$ $\leq$ $(\textrm{right endpoint of }I_{j})$ for any $i \leq j$ and $i,j \in \{1, \dotsc,n\}$.
Similarly, you can define the sorted order based on the left endpoints. However, the sorted order based on these two criteria could be different.

Now, consider the following statement:

a set of n intervals sorted by right and left endpoints

This statement is a bit unclear since the sorted order by left endpoints could be different from the sorted order by right endpoints. However, in Section 1(Introduction) of their paper, they also mention the following statement: &quot;set of $n$ sorted intervals (the $2n$ endpoints of the intervals are sorted). &quot;. Therefore, the sorting by &quot;right and left endpoint&quot; simply means that you are sorting the set of all $2 \cdot n$ points together, i.e., the set: $\{ \ell_{1}, r_{1}, \dotsc, \ell_{n}, r_{n} \}$ is given in sorted order irrespective of point being a left or right endpoint. Furthermore, using this sorted set you can easily recover the sorting of intervals based on (right endpoint) or (left endpoint) in linear time i.e., $O(n)$. This does not change the running time of their coloring algorithm which is $O(n + k)$.