Such coordinates were called canonical because they are those in which equations of motion (or, of the hamiltonian flow of a function $H$) take the “canonical form”
$$
\frac{dq_i}{dt}=\frac{\partial H}{\partial p_i},
\qquad
\frac{dp_i}{dt}=-\frac{\partial H}{\partial q_i}
$$
first written by Poisson (1809, pp. 272, 313), Lagrange (1810, p. 350), and Hamilton (1835, p. 98).
Actually, none of them called that form canonical yet: according to the Encyklopädie (1935, p. 573) the first person to do so was Jacobi (1837, pp. 65-66):
On trouve au moyen de ce
théorème, par le calcul même, des éléments dont les valeurs différentielles, dans
le mouvement troublé, prennent la forme simple qu'elles ont dans le théorème,
forme que je désigne dans mon mémoire sous le nom de canonique.
... and Thomson-Tait (1867, p. 254) commented:
This is the celebrated “canonical
form” of the equations of motion of a system, though why it
has been so called it would be hard to say.
As to the practice of calling the coordinates or “elements” $p_i, q_i$ themselves “canonical”, it seems to originate also with Jacobi in the aforementioned memoir, completed in 1838 but only published posthumously (1862, p. 128; German translation: 1906, p. 153):
Systema
elementorum, quae in modum praecedentium per aequationes differentiales canonicas determinantur, et ipsum dicere convenit canonicum elementorum systema.
While this practice did not universally catch on at first (Thomson-Tait, Poincaré (1893), Whittaker (1917) or the Encyklopädie call the equations canonical, but not the variables), it was adopted by e.g. Donkin (1862, pp. v, 550), Tisserand (1868, p. 258; 1889, p. 164), Schering (1873, p. 23), Lie (1874, p. 258), Routh (1892, pp. 304-306), Dziobek (1892, pp. 102-103), Charlier (1902, pp. 56-58), Dirac (1925, p. 651), etc. In fact it must have leaked somehow between 1838 and 1862, for Cayley has it already in (1858, p. 9):
18. There is, however, one important point which requires to be adverted to. Lagrange, in the memoir of 1810, and the second edition of the ‘Mécanique Analytique,’
remarks, that for a particular system of arbitrary constants, viz., if $\alpha,...$ denote the
initial values of the coordinates $\xi,..$ and $\lambda,..$ denote the initial values of $\smash[b]{\frac{dT}{d\xi'}},...$ then
the equations for the variations of the elements take the very simple form
$$
\frac{d\alpha}{dt}=-\frac{d\Omega}{d\lambda}..,\quad
\frac{d\lambda}{dt}=\frac{d\Omega}{d\alpha},...
$$
This is, in fact, the original idea and simplest example of a system of canonical
elements; viz. of a system composed of pairs of elements, $\alpha, \lambda$, the variations of
which are given in the form just mentioned.