まず http://d.hatena.ne.jp/tetsuyai/20110917/1316234149 あたりを参考に growlnotify を入れます。
after "deploy:restart" do
system("which -s growlnotify && growlnotify -n 'Capistrano' -t 'Capistrano' -m 'デプロイ完了しました。'")
end
which -s でのコマンドの存在チェックと、 -n でアプリケーション名を設定しているところがポイントですかね。