You might find the following link helpful:
Steps to install and set up Aliqueit on an Ubuntu* (or antiX) computer
(including gmp, ecm, ggnfs, msieve, YAFU, Aliqueit)
It will take you through detailed steps to install to any point in the list, the following packages:
gmp
gmp-ecm
ggnfs
msieve (use -r 923 as Batalov suggests - this is not in the instructions)
yafu
aliqueit
factmsieve.py
factMsieve.pl
ecm.py
*It also works with Debian and has instructions for both 32-bit and 64-bit systems. Let me know if something doesn't work...
@Batalov: Thanks! Although I haven't been seriously searching, I wondered where remdups was located...