This is a game I had trubble getting to work. It will function somewhat good without these steps, but it might cause wine to crash (something that never happened to med after I did this).
I could not find any good tutorial for this on the forum (or on the net), so I decided to compile one myself 
Step 1: Getting Wine
For this you need the official build of Wine (not the ubuntu build), in case you haven't already added this repository, this is how you do it:
Open up a terminal and type these commands (for gutsy, if you use a different version of ubuntu, follow the instructions here: Wine Download
):
Code:
wget -q http://wine.budgetdedicated.com/apt/387EE263.gpg -O- | sudo apt-key add -
sudo wget http://wine.budgetdedicated.com/apt/sources.list.d/gutsy.list -O /etc/apt/sources.list.d/winehq.list
sudo apt-get update
sudo apt-get install wine
This build works on both x86 and amd64!
Step 2: Configuring Wine
Grim Fandango will not run in full screen (or windowed, as is made possible by the launcher you will get later), but rather, you need to configure wine to emulate a virtual desktop, and run the game in full screen inside that (which will work best).
Type in your terminal:
Click on the "Graphics" Tab and check "Emulate a virtual desktop", now you need to define the size for this desktop. I prefer 1024x768 since I think it gives me enough room to actually do something, but that is up to you (and the game will scale it anyway).
Now, click "Apply" and close the configuration window
Step 3: Installing Grim Fandango
Now, simply pop the Grim Fandango CD1 into your drive and launch the installation program. Install the game to wherever you like.
Do not install the patch yet! (released by LucasArts to fix some bugs and add Windows XP compability), that comes later!
Step 4: Getting a Custom Launcher
Download and unzip this file
Create the folder .grimfandango in your home directory ("mkdir .grimfandango" in your console), and move "Grim Launcher.exe" to this directory.
Step 5: Setting It Up As a Menu Item
Download this icon to the .grimfandango directory.
Now, type in terminal:
(if you are using Kubuntu, replace gedit with kwrite, if you are using Xubuntu replace it with mousepad)
Code:
sudo gedit /usr/bin/grimfandango
Now, copy paste this into the file (make sure to replace: <yourusername> with your username)
Code:
#!/bin/bash
cd /home/<yourusername>/.grimfandango/
wine Grim\ Launcher.exe
Save and close.
Now, type in terminal:
Code:
sudo chmod +x /usr/bin/grimfandango
Now, type this in your terminal:
Code:
sudo gedit /usr/share/applications/grimfandango.desktop
And copy & paste this into the newly opened file (Again: make sure to replace: <yourusername> with your username):
Code:
[Desktop Entry]
Version=1.0
Encoding=UTF-8
Name=Grim Fandango
Comment=Classic adventure game
Exec=grimfandango
Icon=/home/<yourusername>/.grimfandango/15895.jpg
Terminal=false
X-MultipleArgs=false
Type=Application
Categories=Application;Game;Adventure;
Save and close.
You should now be able to find "Grim Fandango" in your games menu.
Step 6: Starting the Launcher for The First Time
There are still some things to be done for the game to run well. Start the launcher from the menu (notice the emulated desktop around the launcher window).
The Launcher should comment on that you have not installed the patch for the game, and if you would like to do so now. Let it install the patch (this is the only way I got the path installation program to work). Follow the instructions for the installer.
When the patch is installed, click "Options" and then "Run Grim From Hard Drive"
The Launcher will ask you to place CD1 in the drive, do that and let it continue. It may seem to freeze, but it is simply working. After a while it will ask for CD2, pop it in the drive and continue.
The game may crash if you use the CDs while playing.
Step 7: Starting the Game
The Game is now ready for play. Make sure to always start it with the "Play Fullscreen" button.
Known Problems
The game will run fine, but with some flaws.
Your character will leave black tracks where he moves (this isn't to bad though, it will not obstruct the game).
Also, the sound may become funky at times, the only workaround for this that I can find, is to save the game, and restart (the sound should be fine again). This does not happen very often, so it shouldn't be a big problem.
You may sometime find that all keys don't work, just click the game window and it should start working again.
Enjoy the game!!