Amazon EC2にて借りたmicroインスタンスに上記をインストールしてみます。
nginxとgoogleがリリースしたページ表示速度高速化モジュール,
ngx_pagespeedはソースインストールでしかnginxに入れ込むことはできず、
公式でも普通にコンパイルする方法でしか紹介してません。
が、aptにはソースインストールしたものを管理する機能があるらしく、試してみました。
これができると、依存関係で苦しまないで済む気がする！

nginx最新安定版をppaから取得できる状態にする

sudo aptitude install python-software-properties
sudo add-apt-repository ppa:nginx/stable

もろもろに必要なソフトをインストール

sudo aptitude update
sudo aptitude safe-upgrade
sudo aptitude install build-essential zlib1g-dev libpcre3 libpcre3-dev unzip

nginxのソースをダウンロード（ここだけapt-getに注意）

mkdir ~/ngxsrc
cd ~/ngxsrc
sudo apt-get source nginx-full

ngx_pagespeedを持ってくる

cd nginx-1.4.1/debian/modules
wget https://github.com/pagespeed/ngx_pagespeed/archive/release-1.5.27.3-beta.zip
unzip release-1.5.27.3-beta.zip
cd ngx_pagespeed-release-1.5.27.3-beta/
wget https://dl.google.com/dl/page-speed/psol/1.5.27.3.tar.gz
tar -xzvf 1.5.27.3.tar.gz

ビルドオプションを記述する

cd ~/ngxsrc/nginx-1.4.1
nano debian/rules

nginx-fullをインストールするため、その箇所を編集
57行目に下記を追加（せっかくだからcache-purgeもインストール）
cache-purgeは既にパッケージの中に入っている

--add-module=$(MODULESDIR)/ngx_pagespeed-release-1.5.27.3-beta \
--add-module=$(MODULESDIR)/nginx-cache-purge \

以下補足。
Ubuntuのnginxパッケージでは、導入されるモジュールの数により、
nginx-light, nginx-full, nginx-extrasと別れてます。
普通は全部入りのnginx-extrasを導入すればいいのですが、
私は軽量化のため、nginx-fullを指定してビルドオプションを編集しました。
またnginx1.4で対応したので、「--with-http_spdy_module \」を追加してSPDYを有効化。
あと、メールキャッシュサーバ機能は外しました。てか、みんな使ってる？
「--with-mail \」「--with-mail_ssl_module \」を#でコメントアウト。

ビルド前に必要パッケージを揃えてからビルド
（ビルドはec2.microだと超時間かかる。1時間以上かも）

sudo apt-get build-dep nginx
sudo dpkg-buildpackage -b

生成されたdebをインストール

cd ..
sudo dpkg --install nginx-common_1.4.1-1ppa1~precise_all.deb nginx-full_1.4.1-1ppa1~precise_amd64.deb nginx_1.4.1-1ppa1~precise_all.deb

モジュールが入ったか確認してみる

nginx -V

「--add-module=/home/ubuntu/ngxsrc/nginx-1.4.1/debian/modules/ngx_pagespeed」が
出力結果に入っていたら成功！

/etc/nginx/nginx.conf 、/etc/nginx/sites-available/default などを
ご自身の環境に合わせ編集し、サービス再起動しましょう！
（apt管理外インストールだとinit.dも自分で用意せにゃならんから凄く面倒だった…）

sudo service nginx restart