First, what is CryptDB.
A SHORT PRESENTATION, very useful to understand how it works.

Second, reference system: Ubuntu Linux LTS 12.04.x 32bit 64bit (see this comment).

Third, [NEW] installation:

Done. It’s that simple now 😎
If it fails to compile, see THIS comment.

If you still do not succeed see THIS comment.

With recent version of Ubuntu (14.04 and 16.04) you might need to downgrade Bison, see THIS comment.

[OLD] installation:

• install needed packages:
  sudo apt-get install automake bison bzr cmake flex g++ git gtk-doc-tools libaio-dev libbsd-dev libevent-dev libglib2.0-dev libgmp-dev liblua5.1-0-dev libmysqlclient-dev libncurses5-dev libntl-dev libssl-dev
• create a directory, then download software to compile:
  mkdir $HOME/cryptdb-inst
cd $HOME/cryptdb-inst
git clone -b public git://g.csail.mit.edu/cryptdb
wget http://es.csail.mit.edu/mysql-5.5.14.tar.gz
bzr branch lp:mysql-proxy
• compile mysql-proxy:
  cd mysql-proxy
sh ./autogen.sh
./configure --enable-maintainer-mode --with-lua=lua5.1
make
sudo make install
• build CryptDB on MySQL:
  cd $HOME/cryptdb-inst
tar xzf mysql-5.5.14.tar.gz
cp -R cryptdb/parser/mysql_mods/* mysql-5.5.14/
rm mysql-5.5.14/sql/sql_yacc.{cc,h}
cd mysql-5.5.14
mkdir build
cd build
cmake -DWITH_EMBEDDED_SERVER=ON ..
make
sudo make install
cd /usr/local/mysql
sudo chown -R mysql .
sudo cp support-files/my-medium.cnf /etc/my.cnf
sudo scripts/mysql_install_db --user=mysql --basedir=/usr/local/mysql/
sudo /usr/local/mysql/bin/mysqld_safe --lc-messages-dir="/usr/local/mysql/share/english/"
/usr/local/mysql/bin/mysqladmin -u root password 'letmein'

• Build CryptDB:
  cd $HOME/cryptdb-inst/cryptdb
cp conf/config.mk.sample conf/config.mk
sed -i'' -e"1s%/home/nickolai/build%$HOME/cryptdb-inst%" conf/config.mk
make
sudo make install

• now, it’s time to read cryptdb/doc/README, enjoy! 😉

NOTE1: you should create a user mysql to run DBMS for security reasons:
sudo groupadd mysql
sudo useradd -r -g mysql mysql

NOTE2: be very careful on each step and you wont fail.