During my rounds in open-source communities I frequent, I crossed paths with the friendly bunch over at www.ubuntumagazine.net and now it turns out I'm an author at the site! My first order of business was to document the best way to install Nexuiz.
You can view the article here: http://www.ubuntumagazine.net/?p=1984
I hope this helps out our Linux users in using the latest version of Nexuiz. Please let me know if I made any mistakes.