In theory you should be able to install the mono-devel package from Debian, then grab the latest checkout of F#'s Github repository and build. Unfortunately, the most recent versions of Debian's (and Ubuntu's) mono-devel package (3.0.6) include a lovely bug that breaks the F# build (https://bugzilla.xamarin.com/show_bug.cgi?id=10884). Another alternative is installing Debian Sid (unstable branch), where there are currently working F# packages, but installing a whole system from unstable has the sorts of stability issues you might expect, and cherry-picking the right .deb packages from the Debian repositories is unpleasant. There's also the option of using an F# developer's personal repository (https://gist.github.com/tkellogg/5619461), but I don't like adding untrusted sources to my sources.list.
After discovering that Vagrant includes support for a version of Debian Wheezy with F#, I figured out a working, relatively uninvasive approach based on the package versions there and the main F# install instructions (http://fsharp.org/use/linux/).
To build a version of Mono that can successfully compile F#:
sudo apt-get install libtool autoconf g++ gettext make git
sudo apt-get install mono-devel mono-gmcs
git clone git://github.com/mono/mono.git
cd mono
./autogen.sh --prefix=/opt
make
sudo make install
Change /opt to wherever you'd like things to end up (I just like /opt).
Check that you've got the right version:
$ export PATH=/opt/bin:$PATH
$ mono --version
Mono JIT compiler version 3.3.0 (master/cad5315 Fri Aug 16 11:29:02 PDT 2013)
Copyright (C) 2002-2012 Novell, Inc, Xamarin Inc and Contributors. www.mono-project.com
TLS: __thread
SIGSEGV: altstack
Notifications: epoll
Architecture: amd64
Disabled: none
Misc: softdebug
LLVM: supported, not enabled.
GC: sgen
To then build F# against that version:
sudo apt-get install autoconf pkg-config make git
export PATH=/opt/bin:$PATH
export LD_LIBRARY_PATH=/opt/lib:$LD_LIBRARY_PATH
export PKG_CONFIG_PATH=/opt/lib/pkgconfig:$PKG_CONFIG_PATH
git clone https://github.com/fsharp/fsharp
cd fsharp
./autogen.sh --prefix=/opt
make
sudo make install
All three environment variables must be set, not just the PATH; otherwise the just-compiled Mono binaries will be used, but the F# compiler will be built against the standard installation's (incompatible) core libraries. If you get compilation errors about missing abstract members in a type-providers-related file, check that you're finding the right version of the Mono libraries:
$ pkg-config --modversion mono
3.3.0
Then making the environment changes permanent will give you a working F# build on Linux.