I could not find any pre-built binaries (macports) that worked properly out of the box between my laptop and the ubuntu server. So build your own.

NOTE: This will break unison with hosts that use unison 2.40.65 built with ocaml 3.x!

On Ubuntu 12.04

$ sudo apt-get install build-essential linux-headers-$(uname -r)
$ wget -O ocaml-4.00.0.tar.gz http://caml.inria.fr/pub/distrib/ocaml-4.00/ocaml-4.00.0.tar.gz
$ cd ocaml-4.00.0
$ ./configure --with-pthreads
$ make world.opt
$ make install
$ cd ..
$ wget -O unison-2.40.65.tar.gz http://www.seas.upenn.edu/~bcpierce/unison//download/releases/unison-2.40.65/unison-2.40.65.tar.gz 
$ cd unison-2.40.65
$ make UISTYLE=text THREADS=true
###$ make install UISTYLE=text THREADS=true
$ sudo cp ./unison /usr/bin/unison-2.40.65a
$ sudo update-alternatives --install /usr/bin/unison unison /usr/bin/unison-2.40.65a 50
$ update-alternatives --query unison

Link: unison
Status: auto
Best: /usr/bin/unison-2.40.65a
Value: /usr/bin/unison-2.40.65a

Alternative: /usr/bin/unison-2.40.65a
Priority: 50
Slaves:

Alternative: /usr/bin/unison-latest-stable
Priority: 20
Slaves:
 unison.1.gz /usr/share/man/man1/unison-latest-stable.1.gz

On OS X Mountain Lion

Make sure to have installed XCode's command line build tools.

$ wget -O ocaml-4.00.0.tar.gz http://caml.inria.fr/pub/distrib/ocaml-4.00/ocaml-4.00.0.tar.gz
$ cd ocaml-4.00.0
$ ./configure --with-pthreads
$ make world.opt
$ make install
$ cd ..
$ wget -O unison-2.40.65.tar.gz http://www.seas.upenn.edu/~bcpierce/unison//download/releases/unison-2.40.65/unison-2.40.65.tar.gz 
$ cd unison-2.40.65
$ make UISTYLE=text THREADS=true
$ mkdir -p ~/bin
$ make install UISTYLE=text THREADS=true