The guide to installing Strasheela is well-documented, so follow it. A few remarks.

• You'll need g++ and if you want to use the latest snapshot like I do, you'll need Subversion.
• I put the Strasheela source in ~/.strasheela and will use ~/Strasheela for my own files, so set ~/Strasheela/output in ~/.ozrc as a replacement for the /tmp/ output directory.
• Install audacity, cplay, timidity and lilypond (yes, all of it) from the repositories.
• Edit the executables in ~/.ozrc, my suggestion (based on lots of professional experience) would be audacity, cplay, timidity as MIDI player and we'll use evince instead of acroread.
• You'll have to manually install csvmidi and midicsv. Just download the tar.gz and perform the known make, make check, sudo make install cycle.
• The same is true for Fomus, download and install from their website. When compiling from source you'll need libboost-all-dev too (another big one, like Lilypond), from repositories. And lots of memory too. But you'll only need this when you want to export to MusicXML, so you can forget about it for now.
• Add $OZHOME/1.4.99/bin to your $PATH, i.e., ~/.bashrc should contain a line stating export PATH=$PATH:$OZHOME/bin/:\$OZHOME/1.4.99/bin where 1.4.99 is obviously your version of Oz, in case you've followed the installation guide this will be 1.4.99.
• Execute StrasheelaTutorial if you think you're done. If you really want to test your installation (unfortunately not the configuration for some reason), open the tutorial at chapter Output Formats, edit the configuration in File > Settings to match your .ozrc and run the examples.

For reference, here is the relevant part of my .ozrc:

{Init.putStrasheelaEnv csound csound}
{Init.putStrasheelaEnv sndPlayer audacity}
{Init.putStrasheelaEnv cmdlineSndPlayer cplay}
{Init.putStrasheelaEnv csvmidi csvmidi}
{Init.putStrasheelaEnv midicsv midicsv}
{Init.putStrasheelaEnv midiPlayer timidity}
{Init.putStrasheelaEnv lilypond lilypond}
{Init.putStrasheelaEnv 'convert-ly' 'convert-ly'}
{Init.putStrasheelaEnv pdfViewer evince}

I've decided to go for Audacity, if you have another favorite sound editor, pick that. Everything should work now, but I haven't done much with Strasheela at this moment, so if things pop up later, I'll edit these posts accordingly.