On 18 May 2004, Steffen Müller informed us that Pajek nicely runs on Linux via Wine.
Later, Leon Danon prepared a text Pajek on Linux Tutorial. Here is a local copy of Tutorial in PDF.
Wine home page.
In December 2006 Matej Kovačič prepared a tutorial Pajek under Ubuntu (English / Slovene). Here is a local copy of Tutorial in PDF.