DEB-Package based (Ubuntu, Debian, ...): sudo apt-get install wine или Приложения - Установка / Удаление.
RPM-Package based (Mandriva, Fedora, ...): графический интерфейс или yum.
Универсальный способ для GNOME: пользуйся synaptic (Система - Администрирование - Synaptic).
Для KDE: adept.