I love doing the New York Times crosswords, and have had a subscription to the online site for over a decade. On Windows and Mac, they use the AcrossLite program from LitSoft, but their Linux version hasn't been maintained, and I don't even know if it's still available. I know there's XWord, but it doesn't support all the newer features of AcrossLite, like allowing more than one letter per square (a frequent trick in the Sunday puzzles).
I've tried the Windows version of AcrossLite under wine, but it's surprisingly bad.
EDIT (02/11/2011) I contacted LitSoft directly to see if they were ever planning on making the Linux version available again. I received a response right away from a developer. I'm quoting directly from the email:
Yes, Across Lite for Linux will be available again sometime in 1Q2011. We are currently working on a v1.2 re-compile for newer Unix distros as a first-step and will later evolve it to 2.0 version. We tried an Adobe Air version for all platforms other than Windows and Mac but the user experience was terrible partly because of Adobe Air issues so we went back to the native version. Hence the delay.
NY Times recommends (for Linux) http://www.nytimes.com/ref/membercenter/help/litlinux.html
However - with a little searching I found;
http://timesreader.nytimes.com/timesreader/index.html
JClic: puzzles, test exercises, crosswords, you can get it all from Synaptic.