The only reason I still use W indows is to play this game. I tried before and couldnt get it to work on Ubuntu and I wonder if it is possible now.
I personally vote for Playonlinux. Playonlinux is a third party wine wrapper and has the necessary script for AOE2.
You can install Playonlinux by
sudo apt-get install playonlinux
then in Playonlinux install menu choose Age of Empires 2 and prepare your disk with AOE2, then follow the install steps on the screen.